Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
2001-03-15
2003-06-10
Nguyen, Hiep T. (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C711S165000, C375S261000, C375S262000, C375S265000
Reexamination Certificate
active
06578119
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a method and device for memory management in digital data transfer, and especially but not necessarily memory management in the decoding of the digital data of convolution codes.
BACKGROUND OF THE TECHNIQUE
In digital data transfer, it is primarily important to get the departing data to its destination as reliably and flawlessly as possible. One alternative for achieving this, especially in a noise limited? environment, has been to use a larger transmission power. However, regulations made for practical reasons limit the highest permissible transmission power. Another alternative has been to add a redundant information to the transmitted data, which the receiver uses to correct any errors.
In a digital mobile communications network, a received signal also contains noise and channel distortions that cause bit errors, which are then (partly) corrected using an error correction code. The transmitted bit stream can be protected against errors, e.g. as depicted in
FIG. 1
, with a corresponding encoder
10
, which includes the modulo-2 summing units
11
,
12
for forming the convolution code, the shift register
13
-
16
for receiving the bit to be coded, input feed for the bit to be coded
17
and the encoded bit's output bits
18
,
19
. The length (constraint length) of the encoder's shift register is K=4 and the rate is ½, so each bit to be coded
17
is presented as encoded by two output bits
18
,
19
. When a new bit is fed into the shift register
13
-
16
into an element
16
, the bit of the element in question moves to element
15
, the bit of element
15
moves to element
14
and the bit of element
14
moves to element
13
. If in our example the first bit to be transferred to the shift register
16
were 1, the output bits
18
,
19
would be 11. The criteria for the above are that the shift register
13
-
16
is empty (DDDD=0000) in the initial situation. A bit-stream encoded according to
FIG. 1
is decoded on reception for example using a Viterbi algorithm. Other decoding means can also be used.
In digital data transfer, the bit string received must contain some sort of convolution code, i.e. a code containing memory, so that the Viterbi algorithm can be utilised on reception. The Viterbi algorithm performs probability decoding using the Trellis diagram to reduce the need for computation.
FIG. 2
depicts the Trellis diagram
200
formed by the K=4 convolution code, in which the possible initial states
210
-
217
are depicted as status column
201
and the possible end states
220
-
227
are depicted as status column
202
. The encoder's output bits
18
,
19
are depicted as values of branches
230
-
245
. The shift register's
13
-
16
elements mentioned in
FIG. 1
form a status shift, in which the shift register's elements
13
-
15
are the initial status of the Trellis diagram and elements
14
-
16
are the end status of the Trellis diagram, which are reached from the said initial states by feeding a new bit into the encoder's
10
shift register
13
-
16
. Two branches
230
-
245
leave from each state
210
-
217
at the time t=T to the states
220
-
227
at the time t=2T. The corresponding 2-bit number for each branch
230
-
245
, i.e. each branch state
250
-
265
, is compared to the bit pair
18
,
19
encoded with the encoder
10
in FIG.
1
. If, for example, the bits in the encoder's shift register
13
-
16
are 0010, which signifies a state shift from the initial state 001 to the end state 010 when the next bit to be encoded is 1, the shift register's 13-16 bits, i.e. the state shift, are now 0101 (from initial state 010 to end state 101), in which case the encoder transmits as the output bits
18
and
19
,
10
. The Trellis diagram states depicted in
FIG. 2
are utilised in the decoding stage of the data. Several path states formed by branch states formed from individual successive state shifts are stored in the decoder's memory. Each bit pattern to be transmitted corresponding to the branch state is compared to received, possibly incorrect, bits. When receiving new bits, the number of state shifts grows, so the memory must be continuously updated by deleting such paths that are not needed for forming the final bit to be decoded.
In the decoding of convolution codes, a so-called Viterbi decoder depicted in
FIG. 3
is used, which consists of a BMU (Branch Metric Unit)
31
, ACSU (Add-Compare-Select Unit)
32
and SMU (Survivor Memory Unit)
33
. On receiving a bit pair, the BMU
31
calculates the metrics, i.e. the measurement of how far the received bit pair is from each, in this case 16, branch state values
250
-
265
corresponding to the Trellis diagram state shifts. For instance the so-called Hamming distance, i.e. by how many bits the received bits deviate at the time in question from all possible branch metrics corresponding to state shifts, can be used as a measurement. The following example consists of two different states
211
,
215
at the time t=T and correspondingly the states
222
,
223
at the time t=2T. The state of the Trellis diagram at the time t=T is 001 and the received bit pair is 10, in which case the metrics of the state shift 0010 (from state 001 to state 010) is 0, because the received bit pair and the value 10 of the branch in question do not deviate from one another. Another possible state shift 0011 (from state 001 to state 011) with the same received bit pair
10
would give a metric of 2, because both bits of the received bit pair
10
are now different from the branch value 01. The branches
230
-
245
depicting state shifts in
FIG. 2
always correspond to the possible routes of one received bit pair, of which others are more probable than others and the metric must be calculated for each said branch.
The ACSU
32
depicted in
FIG. 3
consists functionally of the Add part, which calculates the cumulative path metric of all paths, i.e. the distance between all possible beginnings and ends of paths; the Compare part, which compares which branch ending in an end state is the more probable choice, i.e. closer to the received bit pair; and the Select part, which selects the more probable branch and stores it to memory. The less probable branch is disqualified and if the other branch that reaches the state in question is disqualified, the entire path leading to the state in question can also be deleted from memory as unnecessary. In the following example the less probable option is disqualified for the other branch as well. As in the previous example, here we will also look at the state shift 0010 from state 001 (
211
) to state 010 (
222
), and the state shift 1011 from state 101 (
215
) to state 011 (
223
). As seen in
FIG. 2
, states 001 and 101 both branch off to states 010 and 011. As was earlier stated, the received bit pair was 10. The branch value in question has two probable state shifts, i.e. state shift 0010 (from state 001 to state 010 and state shift 1011 (from state 101 to state 011). State 010 (t=2T) is reached from both state 001 (t=T) with the value 10 and from state 101 (t=T) with the value 01. If the selection made by the ACSU
32
targets path branch
232
, which runs through states 010 (t=2T) and 001 (t=T), branches
233
,
241
lead to state 011 (t=2T) and branches
240
,
241
leaving from state 101 (t=T) are disqualified. All paths running through states 010 (t=2T), 101 (t=T) (branch
240
), 011 (t=2T) and 101 (t=T) (branch
241
) can now be deleted from the history data. State 101 (t=T) and all paths leading thereto can now be deleted from memory as unnecessary.
In
FIG. 3
, the SMU
33
stores the ACSU's selection data and defines the Trellis diagram final survivor path, which contains the possibly unencoded original bit sequence. An ACSU complying with the prior art is the so-called trace back memory
40
depicted in
FIG. 4
, the memo
Nguyen Hiep T.
Nokia Corporation
Perman & Green LLP
LandOfFree
Method and device for memory management in digital data... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and device for memory management in digital data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and device for memory management in digital data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3145852