Note: Descriptions are shown in the official language in which they were submitted.
CA 02354466 2001-06-12
WO 00/41328 PCT/KR99/00842
DEVICE AND METHOD FOR NORMALIZING METRIC VALUE OF
COMPONENT DECODER IN MOBILE COMMUNICATION SYSTEM
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to an iterative decoding device and
method for a mobile communication system, and in particular, to a device and
method for normalizing a metric value accumulated in a component decoder of an
iterative decoder in a mobile communication system.
2 Description of the Related Art
In general, iterative decoding is employed in mobile communication
systems such as an IMT-2000 (or CDMA-2000 and UMTS) system, which use a
turbo code. Also, iterative decoding is employed in deep space communication
systems and satellite communication systems, which use concatenated
convolutional codes, concatenated block codes or product codes. The technical
field of iterative decoding is related to soft decision and optimal
performance of an
error correction code.
FIG. 1 shows a common iterative decoder comprising two component
decoders. Referring to FIG. 1, a first component decoder 101 receives
systematic
code signals Xk, a first parity signal Y,k provided from a demultiplexer 107
(which
demultiplexes input parity signals Yk), and a first extrinsic information
signal. The
first component decoder 101 performs decoding on the received signals to
output a
primarily decoded signal relating to the decoding results. The signal is made
up of
the systematic code signals Xk ingredient and a second extrinsic information
ingredient. An interleaver 103 interleaves the primarily decoded signal. A
second
component decoder 105 receives the primarily decoded signal output from the
interleaver 103 and a second parity signal Yzk provided from the demultiplexer
107.
The second component decoder 105 decodes the received primarily decoded
signals and the second parity signal Y2k to output a secondarily decoded
signal to a
deinterleaver 111. Further, the second component decoder 105 provides the
extrinsic information ingredient to the first component decoder 101 through a
deinterleaver 109.
As illustrated in FIG. 2, the first component decoder includes a branch
metric calculation part (BMC) 113 for performing branch metric calculation and
an
CA 02354466 2001-06-12
WO 00/41328 PCT/KR99/00842
-2-
add & compare & selection part (ACS) 115 for performing metric calculation and
comparison in each state to select a path having fewer errors.
In general, such an iterative decoder calculates a metric value M~ in
accordance with Equation 1 below.
N
Mt = M,_, + u~ x Lc x y~,~ + ~ x,, j x Lc x y~,j + u, x L(u~ ) Eq. 1
j~2
where, Mt : accumulated metric value for time t,
u~ : codeword for the systematic bit, codeword for each bit of Xk
xt~ : codeword for the redundancy bit,
y~ : received value for the channel (systematic + redundancy),
Lc : channel reliability value, and
L(u~) : a-prior reliability value for time t
It is noted from Equation 1 that, with each metric calculation, the metric
value M~ continuously grows due to the second, third and fourth terms. For
hardware implementation, the metric values should have a value within a
specific
range to avoid an overflow problem. However, the fundamental purpose of
iterative decoder is to perform iterative decoding in order to improve
decoding
performance (i.e., BER (Bit Error Rate) or FER (Frame Error Rate)). Thus, in
order for the iterative decoder to accomplish its purpose after successive
iterations,
the metric values may increase to exceed a specific range. Thus, if a specific
range for the metric values is presumed when designing the hardware of the
decoder, the metric value may exceed the range and create an overflow problem.
SUMMARY OF THE INVENTION
It is, therefore, an object of the present invention to provide a device and
method for normalizing a metric value of a component decoder, wherein when all
the accumulated metric values of the present states exceed a threshold value,
the
accumulated metric values are normalized to a given level after subtracting a
specific value therefrom.
To achieve the above object, there is provided a decoder using transition of
a plurality of metric values at a plurality of time durations. The decoder
comprises
a decision circuit that generates a decision signal when the metric values all
exceed
CA 02354466 2001-06-12
WO 00/41328 PCT/KR99/00842
-3-
a predetermined value. A subtracter subtracts the predetermined value from the
metric values in response to the decision signal so as to normalize the metric
values. The decision circuit includes a plurality of memories for storing the
corresponding metric values with a predetermined number of bits. A NAND gate
provides the decision signal (a "1" or a HIGH signal) when the most
significant bit
(MSB) values provided in the respective memories are all "1" (HIGH). The
subtracter resets the MSB in each memory when the NAND gate outputs a HIGH
decision signal, thus subtracting a predetermined amount from each metric
value.
BRIEF DESCRIPTION OF THE DRAWINGS
The above and other objects, features and advantages of the present
invention will become more apparent from the following detailed description
when
taken in conjunction with the accompanying drawings in which:
1 S FIG. 1 is a block diagram illustrating an iterative decoder including two
component decoders;
FIG. 2 is a detailed block diagram illustrating the component decoders of
FIG. 1;
FIG. 3 is a schematic diagram illustrating an ACS of a component decoder
having a metric value normalization device in ACS of component decoder
according to a first embodiment of the present invention;
FIG. 4 is a flow chart illustrating a metric value normalization procedure
according to the first embodiment of the present invention;
FIG. S is a diagram illustrating the ACS of a component decoder having a
2S metric value normalization device in ACS of component decoder according to
a
second embodiment of the present invention;
FIG. 6 is a diagram illustrating a format of a metric value storing memory
for normalizing the metric values according to the second embodiment of the
present invention;
FIG. 7 is a flow chart illustrating a metric value normalization procedure
according to the second embodiment of the present invention;
FIGS. 8A and 8B are diagrams illustrating a correct path, an incorrect path
and a path difference in-between and quantization mapping for the code
symbols;
FIGS. 9A to 9C are diagrams illustrating a correct path and an incorrect
3S path according to a signal-to-noise ratio; and
FIG. 10 is a diagram illustrating 0",~X value in a saturated state as a
function of an energy-to-noise power ratio Eb/No.
CA 02354466 2001-06-12
WO 00/41328 PCT/KR99/00842
-4-
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT
The ACS for the component decoder according to the present invention
normalizes the metric values after subtracting a specific value therefrom when
the
metric values exceed a threshold value.
There are two methods for normalizing the accumulated metric values
according to the present invention. With respect to the first method, when one
of
the accumulated metric values of the respective states exceeds a threshold
value,
the accumulated metric values are normalized using the minimum accumulated
metric value. With respect to the second method, when all the accumulated
metric
values exceed the threshold value, the accumulated metric values are
normalized
using a predetermined value.
The nomalization for ACS of the present invention may replace the
nomalization for ACS 115 of the iterative decoder 101 described above with
respect to FIG. 2.
A. First Embodiment
With reference to FIG. 3, the first embodiment will now be described. FIG.
3 shows a structure of the ACS having a metric value normalization device for
a
constraint length K=3 according to a first embodiment of the present
invention.
Referring to FIG. 3, the metric value normalization device will be
described. FIG. 3 shows four "present states", each having a metric value. For
K=3 for the metric values, the number of shift registers is 2 and the number
of
possible states is 4. A comparator 117 having a threshold value detects the
metric
value of each state. When the detected metric values all exceed the threshold
value,
the comparator 117 outputs a specific value to adders 125a-125d, each adder
being
connected between one present state and one next state. The adders 125a-125d
then subtract the specific value from the accumulated metric values of the
present
states and then output the resulting values to the next states. The term
"accumulated metric values of the present state" is used interchangeably with
"metric values of the present state" in the description to underscore that the
metric
values of the present state accumulate with successive metric calculation.
FIG. 4 shows a procedure for normalizing metric values according to the
CA 02354466 2001-06-12
WO 00/41328 PCT/KR99/00842
-5-
first embodiment of the present invention. Referring to FIG. 4, the comparator
117
detects metric values for the four present states in step 401. After detecting
the
metric values, the comparator 117 examines in step 403 whether at least one of
the
detected accumulated metric values exceeds the threshold value. When any one
of
the accumulated metric values does not exceed the threshold value, the
comparator
117 proceeds to step 407 to perform normal ACS operation. If at least one of
the
accumulated metric values exceeds the threshold value, the comparator 117
outputs the minimum of the four detected accumulated metric values to the
adders
125a-125d, in step 405. The adders 125a-125d then subtract the minimum
accumulated metric value from all four accumulated metric values, and then
transitions to the next states. Thereafter, as represented in step 407, the
decoder
then proceeds with its usual ACS operation.
B. Second Embodiment
The second embodiment is described below.
FIG. 5 shows a structure of a nomalization block of an ACS according to
the second embodiment of the present invention. Referring to FIG. 5, the
comparator comprises a plurality of memories 130, 132, I34 and 136 for storing
the accumulated metric values of the respective states, an AND gate 121 for
determining whether all the accumulated metric values stored in the memories
130,
132, 134 and 136 exceed a threshold value, and an inverter 119 for resetting
the
most significant bit (MSB) of the respective memories 130, 132, 134 and 136 in
response to a HIGH signal output from the AND gate 121.
A format of the memories is described with reference to FIG. 6. It will be
assumed herein that each accumulated metric value uok , u,k , u2k , u3k has 8
bits per
sample plus one additional bit for preventing overflow of the accumulated
metric
value. Thus, the accumulated metric value has 9 bits per sample in total.
Referring
back to Fig. 5, the AND gate 121 receives the ninth bit which is the most
significant bit (MSB) of memories 130, 132, 134 and 136, and generates a HIGH
output signal when all the input signals are '1'. That is, when any one of the
MSBs
from the memories 130, 132, 134 and 136 is not '1', the AND gate 121 generates
no output signal (a "LOW" signal). When all the MSBs from the memories are
"HIGH" or ' 1', the AND gate 121 generates a HIGH signal. When AND gate 121
outputs a HIGH signal, the inverter 119 outputs a reset signal to the MSBs of
the
memories 130, 132, 134, 136, thereby resetting the MSBs. This is equivalent to
CA 02354466 2001-06-12
WO 00/41328 PCT/KR99/00842
-6-
subtracting the value of 256 from each accumulated metric value, thus allowing
the
accumulated metric values to be expressed with 8 bits.
Further, assume that a difference between the accumulated metric values
of two states is Ok = {u;k -u~k) 5 0""x, where i and j are one of 0, 1, 2 and
3 and k
is an arbitrary time point. In addition, it is assumed that the maximum
difference
between accumulated metric values of two states ~X 255=28-1. Finally, it is
assumed that u,~ is a metric value having the minimum value and u,k is a
metric
value having the maximum value, as shown in FIG. 6.
With regard to underflow, when MSBs of the metric values at the time k
are all '1', the minimum value is 256. For example, since the minimum value is
' 100000000' (=256), even resetting the MSBs will not cause underflow.
On the above assumptions, if the MSB of u3k is '1', the MSB of the other
states are either '0' or '1'. Until all the MSBs of u;k (where OSi<-3) become
'1', no
carry-out occurs even though the MSB of u,k (and possible one or two other
metric values) is "1". That is, until all the MSBs become '1', no carry-out
occurs at
the ninth bit for any of them. This means that O'' does not exceed ~X.
FIGs. 7 gives a flowchart illustrating the procedure for normalizing the
metric values according to the second embodiment. Referring to FIGS. 5 and 7,
in
step 501, a comparator 117 detects accumulated each metric values, in concrete
terms, the AND gate 121 in the comparator l I7a detects (or receives} the MSBs
of
the accumulated metric values of the respective present states. Upon receipt
of the
MSBs of the present states, the comparator 117 determines whether all the
accumulated metric values of the respective present state is over the
threshold time.
That is, the AND gate 121 of the comparator 117 determines whether all the
MSBs
are ' 1', as represented in decision block 503. When any one of the MSBs is
not ' 1',
the comparator 117a proceeds to step 507 to perform normal ACS operation. When
all the MSBs of the accumulated metric values are ' 1', the comparator 117a
proceeds to step 505, where the threshold value is subtracted from each metric
value, thereby proceeding with step 505. That is, all of the MSBs are reset.
This
corresponds to the AND gate 121 providing a HIGH signal to the inverter 119
and
the inverter 119 in response outputting a reset signal to the MSBs of the
respective
accumulated metric values, thus resetting the MSBs. After resetting the MSBs,
the
comparator 117a performs the normal ACS operation, as shown in step 507.
CA 02354466 2001-06-12
WO 00/41328 PCT/KR99/00842
A further description is now made of ~ referred to above, with reference
to FIGS. 8A to 10. With 0''<~, overflow does not occur. ~X has a lower value
at the low EblNo, and has a higher value at the high Eb/No. That is, the
difference
between the metric values has the lower value at the low Eb/No and higher
value at
the high Eb/No. This is because the noise is increased at the low Eb/No,
decreasing
the difference, and the noise is negligible at the high Eb/No, increasing the
difference ~ between the metric values. Therefore, it is very important how to
set the ~",aX value at the high Eb/No. In the first instance, it can be simply
considered that ~ is infinite when EblNo is infinite. However, for example, in
a
SOVA (Soft Output Viterbi Algorithm), the metric difference is limited to a
constant determined by due.
For example, assume 4 bits per sample, a code rate R=1/3, K=9, and a
convolutional code transmits an all-zero codeword of '000'. In this case, for
the
high Eb/No, most errors occur during comparison/selection between an all-zero
path and a dfree path, as shown in FIG. 8A. Here, a branch metric value and a
path
metric value are calculated by Equations 2 and 3 below, respectively.
3
BM~,> _ ~ Ck,, x y~r>t~ Eq. 2
1=1
N 3
PM~k, _ ~ ~ Ck.r x Y~ok~ = uw. Eq. 3
k~l l=1
where 1=0, 1, 2 and 3, Ck,, is a codeword, y~;~k,~ is a received signal, k is
a given
time, l is a codeword index, and i is a relative index.
Therefore, 0; k = u; s~k - u; ''k < 0 "~x , where 's' denotes a survivor path
and
'c' denotes a competition path. It is necessary to calculate ~X at the high
EblNo
where O;k has the maximum value. This means that if O;k is lower than ~X at
the high Eb/No where O;k has the maximum value, the difference between the
metric values does not exceed fix.
In a given state 'i', there exists a metric difference between the two paths
of the all-zero path and the dfr~ path. FIG. 8B shows that the difference
between
the two paths depends on the dfree code symbol.
CA 02354466 2001-06-12
WO 00/41328 PCT/KR99/00842
_g_
In other words, the survivor path metric is a value obtained by adding a
path metric for the zero path to a metric value in a first state at a previous
time
point, and the competition path metric is a value obtained by adding a path
metric
according to the competition path to a metric value in a second state at the
previous
time point. At this point, since a path metric between the second state and
the
comparison time is larger than a path metric between the first state and the
comparison time, the difference ~X is equal to or larger than O;k . Therefore,
when ~ is satisfied, ~;k is also satisfied. That is, that the difference does
not
exceed 0",aX means that the metric value difference between the two states at
the
above time point does not exceed ~X.
The metric difference is given as follows:
(C.C (Convolutional Coder) 's die=18 for K=9, R=1/3)
fix= a ~.k - a ~.k
=~M-(M+df,ee x 15)~
=~d~e x 15,=18 x 15=270
where M denotes a metric value at a branch point of the survivor path and the
competition path. Therefore, when a condition of ~X<_270 is satisfied, the
difference value between the respective states does not exceed ~. Since it is
assumed there are 4 bits per sample, the number of memories for storing the
metric
value is 8, and since a 1-bit memory is added to prevent overflow, ~=29=512.
Since 270<512, the above condition is satisfied.
FIG. 9A shows the ~X value at the high signal-to-noise ratio, and the ~X
value is calculated by
~X d~exMax(Q[ctot]) ~~~~ (4)
where Q denotes a quantization level, and Max(Q[.]} denotes a distance between
'0' and '1'. For example, for 4 bits per sample, Q=16 and Max(Q[.])=15, and
for 3
bits per sample, Q=8 and Max(Q[.])=7.
FIG. 9B shows the ~x value at the medium signal-to-noise ratio, and the
~X value at this time is calculated by
CA 02354466 2001-06-12
WO 00/41328 PCT/KR99/00842
-9-
4~X (~~+s)xMax(Q[.]) .... Eq, 5
where S caused by noises has a very small value, and is smaller than or equal
to
2xdfreexMax(Q[.]) in the C.C. However, there does not happen a case where 8 is
added as in Equation 5.
FIG. 9C shows the g"ax value at the low signal-to-noise ratio, and the ~
value at this time is calculated by
tl~,~,~=(due-8)xMax(Q[.]) ~~~~ (6)
Therefore, as shown in FIG. 10, it is noted that the ~X value increases
little by little with the Eb/No and is saturated beginning at a certain point.
When
0",~X satisfies Equation S, Equation 6 is also satisfied.
Next, a description will be made of the C.C's characteristics in the
CDMA-2000 system.
For K=9 and R=1 /2, die 12 and the next d~e~ 14,16,18,20
For K=9 and R=1/3, die 18 and the next d~e~20,22
For K=9 and R=1/4, d~.ee 24 and the next dfree~26,18
Table 1 below shows the 0",~X value in the C.C.
Table 1
C.C Characteristicst1~ (Previous ~X (Next die)
die)
K=9, R=1/2 15x12=180 210(15x14) - 240(15x16)
R=1/3 15x18=270 300(15x20) - 330(15x22)
R=1/4 15x24=360 390(15x26) - 420(15x28)
Therefore, the number of bits to be added to prevent overflow of 8
bits/sample allocated for the metric values is determined as follows:
For R=1/2, the bit number is 1 because 28=256 and 180<256; for R=1/3,
the bit number is 2 because 29=512 and 270<512; and for R=1/4, the bit number
is
2 because 29=S 12 and 360<512. In other words, since 8 bits are required for a
code
rate R=1/2, it is necessary to add only 1 bit to prevent overflow. Further,
since 9
CA 02354466 2001-06-12
WO 00/41328 PCT/KR99/00842
- 10-
bits are required for a code rate R=1/3, it is necessary to add only 1 bit. In
addition,
since 9 bits are required for a code rate R=1/4, it is necessary to add 1 bit.
Therefore, it is possible to prevent overflow by adding only 1 bit to the
number of
bits required according to the code rate.
As described above, the novel device can prevent errors due to overflow
by normalizing the accumulated metric values for decoding, thereby increasing
efficient use of the memory.
While the invention has been shown and described with reference to a
certain preferred embodiment thereof, it will be understood by those skilled
in the
art that various changes in form and details may be made therein without
departing
from the spirit and scope of the invention as defined by the appended claims.
