Title: System of and method for decoding trellis codes
Abstract: Systems and related methods are described for (1) determining one or more state probabilities for one or more states in a trellis representation; (2) determining an estimate of or extrinsic output for a bit using a trellis representation; (3) performing a MAX* 2->1 operation; and (4) computing forward state probabilities in a forward mode of operation and computing backward state probabilities in a backward mode of operation. Combinations of the foregoing are also described.
Patent Number: 6,973,615 Issued on 12/06/2005 to Arad, et al.
| Inventors:
|
Arad; Eran (Misgav, IL);
Dalumi; Efraim (Misgav, IL);
Kons; Shachar (Haifa, IL);
Eidson; Donald B. (San Diego, CA)
|
| Assignee:
|
Conexant Systems, Inc. (Newport Beach, CA)
|
| Appl. No.:
|
013490 |
| Filed:
|
December 13, 2001 |
| Current U.S. Class: |
714/792 |
| Intern'l Class: |
H03M 013/03 |
| Field of Search: |
714/786,755,791-796
375/341,262
|
References Cited [Referenced By]
U.S. Patent Documents
Other References
Pietrobon, S.S., Implementation and Performance of a Turbo/Map Decoder, International
Journal of Satellite Communications, vol. 16, pp. 23-46 (1998).
Robertson, P. and Worz, T., Extensions of Turbo Trellis Coded Modulation to
High Bandwidth Efficiencies, Institute for Communication Technology, pp. 1251-1255 (1997).
Cherubini, G. and Olcer, S., Concatenated Coding for Binary Partial-Response
Channels, Zurich Research Laboratory, IBM Research Division, pp. 1789-1794 (1994).
Bahl, L. R., et al., Optimal Decoding of Linear Codes for Minimizing Symbol
Error Rate; IEEE Transactions on Information Theory, Mar. 1974, pp. 284-287.
Benedetto, S. and Montorsi, G., Serial concatenation of block and convolutional
codes, Electronics Letters, vol. 32, No. 10, May 1996, pp. 887-888.
Benedetto, S. and Montorsi, G., Iterative decoding of serially concatenated
convolutional codes; Electronics Letters, vol. 32, No. 13, Jun. 1996, pp. 1186-1188.
Benedetto, S., et al., A Soft-Input Soft-Output Maximum A Posteriori (MAP)
Module to Decode Parallel and Serial Concatenated Codes; TDA Progress Report
42-127, Nov. 1996, pp. 1-20.
Benedetto, S. et al., Serial Concatenated Trellis Coded Modulation with Iterative
Decoding: Design and Performance, submitted to IEEE Comm. Theory Mini Conference
97 (Globecom 97), pp. 38-43.
Benedetto, S., and Divsalar, D., Turbo Codes: Analysis, Design, Iterative
Decoding and Applications, Course 909, Part II, International Courses for Telecom
and Semiconductor Professionals, Oct. 25-29, 1999, Barcelona, Spain, pp. 324-339.
Berrou, C., et al., Near Shannon Limit Error—Correcting Coding and Decoding:
Turbo-Codes (1); IEEE, 1993, pp. 1064-1070.
Divsalar, D. and Pollara, F., Serial and Hydrid Concatenated Codes with Applications;
Jet Propulsion Laboratory, California Institute of Technology, pp. 1-8.
Divsalar, D. and Pollara, F., Turbo Trellis Coded Modulation with Iterative
Decoding for Mobile Satellite Communications; Jet Propulsion Laboratory, California
Institute of Technology, pp. 1-7.
Divsalar, D., et al., Serial Turbo Trellis Coded Modulation with Rate-1 Inner
Code, Jet Propulsion Laboratory, California Institute of Technology, Jun. 2000,
p. 194.
Divsalar, D., et al., Serial Concatenated Trellis Coded Modulation with Rate-1
Inner Code, IEEE, 2000, pp. 777-782.
Hagenauer, J. and Hoeher, P., A Viterbi Algorithm with Soft-Decision Outputs
and its Applications; Proceedings of IEEE Globecom '89; Dallas, Texas, Nov.
1989; pp. 47.1.1-47.1.7.
Hoeher, Peter and Lodge, John, "Turbo DPSK": Iterative Differential PSK Demodulation
and Channel Decoding; IEEE Transactions on Communications, vol. 47, No. 6,
Jun. 1999, pp. 837-843.
Narayanan, K. R. and Stüber, G. L., A Serial Concatenation Approach to
Iterative Demodulation and Decoding; IEEE Transactions on Communications, vol.
47, No. 7, Jul. 1999, pp. 956-961.
Nill, C. and Sundberg, C.W., List and Soft Symbol Output Viterbi Algorithms:
Extensions and Comparisons, IEEE Transactions on Communications, vol. 43, Nos.
2/3/4, Feb./Mar./Apr., pp. 277-287.
Peleg, M. et al., On Interleaved, Differentially Encoded Convolutional Codes,
IEEE Transactions on Information Theory, vol. 45, No. 7, Nov. 1999, pp. 2572-2582.
Robertson, P., et al., A Comparison of Optimal and Sub-Optimal MAP Decoding
Algorithms Operating in the Log Domain; IEEE, 1995, pp. 1009-1013.
Viterbi, A., An Intuitive Justification and a Simplified Implementation of
the MAP Decoder for Convolutional Codes; IEEE Journal on Selected Areas in
Communications, vol. 16, No. 2, Feb. 1998, pp. 260-264.
|
Primary Examiner: Chase; Shelly
Attorney, Agent or Firm: Howrey LLP
Parent Case Text
This application claims the benefit of U.S. Provisional Application No. 60/386,197,
filed Nov. 13, 2001, U.S. Provisional Application No. 60/327,257, filed Oct. 4,
2001, and U.S. Provisional Application No. 60/255,874, filed Dec. 15, 2000, each
of which is hereby fully incorporated by reference herein as though set forth in full.
RELATED APPLICATIONS
This application is related to co-pending U.S. patent application Ser. No. 10/013,492,
filed on even date herewith, U.S. Provisional Application No. 60/386,182 Nov. 13,
2001 U.S. Provisional Application No. 60/327,258, filed Oct. 4, 2001, and U.S.
Provisional Application No. 60/255,797, filed Dec. 15, 2000, each of which is owned
in common by the assignee hereof, and each of which is hereby fully incorporated
by reference herein as though set forth in full.
SUMMARY
The invention provides ba system for determining one or more state probabilities
for one or more states in a trellis representation. In one embodiment of the system,
branch metric logic determines branch metrics for one or more of the branches between
one or more states in a first portion of the trellis and one or more states in
a second portion of the trellis, and state probability logic determines state probabilities
for one or more of the states. In one embodiment, the system concurrently normalizes
the one or more state probabilities responsive to assertion of a normalization
control signal. In one implementation, the state probability logic determines a
state probability for a state by deriving branch values for one or more branches
exiting or entering the state, and then derives the state probability by performing
a group operation on the branch values. In one implementation example, the group
operation is the MAX* operation.
In a second embodiment, the state probability logic comprises p state probability
logic modules for determining in parallel state probabilities for each of p states,
where p is an integer of two or more. In one embodiment, the system concurrently
normalizes the one or more state probabilities responsive to assertion of a normalization
control signal.
The invention also provides a system for determining an estimate of or extrinsic
output for each of one or more bits. In one embodiment, the system iterates for
each of the bits. In this embodiment, during a particular iteration, the system
derives state values for each of one or more states in a trellis representation,
where the state value for a state is derived from the forward state probability
and the backward state probability for the state. Then, it derives a first value
by performing a group operation on the state values for each of the states which
imply release of a logical "1" for the bit, and second value by performing a group
operation on the state values for each of the states which imply release of a logical
"0" for the bit. It then derives an estimate of or extrinsic output for the bit
from the first and second values. In one implementation, the group operation is
the MAX* operator. In one implementation example, the system derives an estimate
of the bit by subtracting the second value from the first and comparing the difference
with a threshold of 0. If the difference equals or exceeds the threshold, the estimate
is taken to be a logical "1". If the difference is less than the threshold, the
estimate is taken to be a logical "0".
In a second embodiment, during a particular iteration, the system derives a branch
values for each of one or more branches in the trellis representation, where the
branch value for a branch is derived from the forward state probability of the
originating state for the branch, the branch metric for the branch, the backward
state probability for the terminating state of the branch, and, possibly, the a
priori probability. The system derives a first value by performing a group operation
on the branch values for each of the branches which imply release of a logical
"1", and a second value by performing a group operation on the branch values for
each of the branches which imply release of a logical "0". It then derives the
estimate or extrinsic output for the bit from the first and second values. In one
implementation, the group operator is the MAX* operator. In one implementation
example, the system derives an extrinsic output for the bit from the difference
between the first and second values.
The invention further provides a system for computing the MAX* of operands A
and B. In one embodiment, first logic in the system tests the difference A-B relative
to zero, and outputs a signal indicative thereof.
Second logic in the system determines the maximum of the operands A and B,
MAX(A,B), by outputting a signal representative of the operand A if the signal
from the first logic indicates that the difference A-B is greater than zero, and
outputs a signal representative of the operand B otherwise.
Third logic in the system outputs a value corresponding to ln(1+exp(-|A-B|)).
Fourth logic derives the output of the system from the sum of the outputs of the
second and third logic while normalizing the output responsive to assertion of
a normalization control signal.
The invention further provides a system for computing one or more state probabilities
for the states in a trellis representation. This trellis representation has one
or more branches between one or more states in a first portion of the trellis and
one or more branches in a second portion of the trellis.
In one embodiment, branch metric logic in the system computes one or more branch
metrics for one or more of the branches, and indication logic in the system indicates
whether the system is configured to compute forward state probabilities or backward
state probabilities.
State probability logic in the system (1) computes one or more forward state
probabilities of one or more states in the second portion of the trellis, while
normalizing the state probabilities responsive to assertion of a normalization
control signal, provided the indication logic indicates the system is configured
to compute forward state probabilities; and (2) computes one or more backward state
probabilities of one or more states in the first portion of the trellis, while
normalizing the state probabilities responsive to assertion of a control signal,
provided the indication logic is configured to compute backward state probabilities.
In one implementation example, the system is part of a log-MAP decoder, and there
are five states in the trellis at a time. In this implementation example, each
branch is associated with one encoder input bit and two encoder output bits. Moreover,
only two branches enter and exit each of the states at a time. A total of 64 branches
correspond to a particular portion of the trellis.
In this implementation example, there are 32 instances of state probability logic,
one for each of the 32 states in the trellis. Each instance may be configured to
operate in a forward mode or a backward mode.
When the state probability logic for a particular state is configured to operate
in the backward mode, the backward state probability for the state may be computed
by first determining for each of the two branches exiting the state a branch value
equal to the sum of the backward state probability of the terminating state of
the branch and the branch metric for the branch. The backward state probability
for the state is then derived from the MAX* of the branch values for each of the
two branches exiting the state.
Similarly, when the state probability logic for a particular state is
configured to operate in the forward mode, the forward state probability for the
state may be computed by first determining for each of the two branches entering
the state a branch value equal to the sum of the forward state probability of the
originating state of the branch and the branch metric for the branch. The forward
state probability for the state is then derived from the MAX* of the branch values
for each the two branches entering the state.
Meanwhile, normalization control logic is configured to evaluate the most
significant bits of the 64 branch values which are computed by the 32 renderings
of the state probability logic at a time. If the most significant bits of any one
of these 64 branch values equals or exceeds a constant, a normalization control
signal is asserted. Responsive to the assertion of this normalization control signal,
the 32 renderings of the state probability logic are configured to concurrently
normalize the state probabilities.
In this implementation example, once the forward and backward state probabilities
for a portion of the trellis have been computed, estimation logic is configured
to determine an estimate of the encoder input bit associated with a particular
portion of the trellis. In this implementation example, because of the code structure,
all the branches entering the first 16 states of the trellis imply release of a
logical "1" for the bit, and all the branches entering the next 16 states of the
trellis imply release of a logical "0" for the bit. In this implementation, a state
value is derived for each of the states equal to the sum of the forward and backward
state probabilities for the state. A first value is then derived from the MAX*
of the state values for the first 16 states of the trellis, and a second value
is derived from the MAX* of the state values for the next 16 states of the trellis.
The second value is then subtracted from the first value, and the resulting difference
compared with a threshold of 0. If the difference equals or exceeds the threshold,
the estimate is taken to be a logical "1". If the difference is less than the threshold,
the estimate is taken to be a logical "0".
Also in this implementation example, once the forward and backward state probabilities
for a particular portion of the trellis have been computed, extrinsic output logic
is configured to determine an extrinsic output for each of the two encoder output
bits associated with the particular portion of the trellis, one bit at time. In
this implementation example, two iterations are performed, one for each of the
two output bits. During a particular iteration, for each of the 64 branches that
are present in the corresponding portion of the trellis, the system compute a branch
value equal to the sum of the forward state probability of the originating state
of the branch, the backward state probability of the terminating state of the branch,
and the difference between the branch metric for the branch and the a priori probability
for the bit.
A first value may then be derived from the MAX* of the branch values for each
of
the branches which imply release of a logical "1" for the bit in question, and
a second value may be derived from the MAX* of the branch values for each of the
branches which imply release of a logical "0" for the bit in question. The second
value may be subtracted from the first to form an extrinsic output for the bit
in question. This process may then repeated for the second encoder output bit.
Method counterparts to each of these systems are also provided. Other systems,
methods, features and advantages of the invention will be or will become apparent
to one with skill in the art upon examination of the following figures and detailed
description. It is intended that all such additional systems, methods, features
and advantages be included within this description, be within the scope of the
invention, and be protected by the accompanying claims.
Claims
1. A system for determining one or more state probabilities for one or more states
in a trellis representation, the system comprising:
branch metric logic for determining one or more branch metrics for one or more
branches between one or more states in a first portion of the trellis and one or
more states in a second portion of the trellis; and
state probability logic for determining one or more state probabilities for one
or more of the states, comprising:
first logic for determining for each of one or more branches a branch value,
a branch connecting an originating state with a terminating state, the originating
state having a forward state probability and the terminating state having a backward
state probability, wherein a branch value for a branch is either the sum of the
forward state probability of the originating state of the branch and the branch
metric for the branch or the backward state probability of the terminating state
of the branch and the branch metric for the branch; and
second logic for deriving a state probability for a state from a group operation
performed on the branch values for one or more branches.
2. The system of claim 1 wherein the group operation is MAX*.
3. The system of claim 1 wherein a forward state probability for a state is derived
from the MAX* of the branch values for each of the branches entering the state,
wherein the branch value for a branch is the sum of the forward state probability
of the originating state of the branch and the branch metric for the branch.
4. The system of claim 1 wherein a backward state probability for a state is
derived from the MAX* of the branch values for each of the branches exiting the
state, wherein the branch value for a branch is the sum of the backward state probability
of the terminating state of the branch and the branch metric for the branch.
5. A system for determining one or more state probabilities for one or more states
in a trellis representation, the system comprising:
branch metric logic for determining one or more branch metrics for one or more
branches between one or more states in a first portion of the trellis and one or
more states in a second portion of the trellis; and
state probability logic for determining one or more state probabilities for one
or more of the states, comprising:
first logic for determining for each of one or more branches a branch value,
a branch value for a branch being derived from one or more state probabilities
and branch metric of the branch; and
second logic for deriving a state probability for a state from a group operation
performed on the branch values for one or more branches,
wherein the state probability logic is configured to concurrently normalize state
probabilities responsive to assertion of a normalization control signal.
6. The system of claim 5 further comprising normalization control logic for asserting
the normalization control signal responsive to an evaluation of selected bits from
one or more branch values.
7. The system of claim 6 wherein the normalization control logic is configured
to assert the normalization control signal responsive to a comparison of the most
significant bits of the one or more branch values with a predetermined threshold.
8. The system of claim 7 wherein the normalization control logic is configured
to assert the normalization control signal responsive to an evaluation of the most
significant bits of the branch values for each of the branches between the first
and second portions of the trellis.
9. A system for determining one or more state probabilities for one or more states
in a trellis representation, the system comprising:
branch metric means for determining one or more branch metrics for one or more
branches between one or more states in a first portion of the trellis and one or
more states in a second portion of the trellis; and
state probability means for determining one or more state probabilities for one
or more of the states, comprising:
first means for determining branch values for each of one or more branches, a
branch connecting an originating state with a terminating state, the originating
state having a forward state probability and the terminating state having a backward
state probability, wherein a branch value for a branch is either the sum of the
forward state probability of the originating state of the branch and the branch
metric for the branch or the backward state probability of the terminating state
of the branch and the branch metric for the branch; and
second means for deriving a state probability for a state from a group operation
performed on the branch values for one or more branches.
10. A system for determining one or more state probabilities for one or more
states in a trellis representation, the system comprising:
branch metric logic for determining one or more branch metrics for one or more
branches between one or more states in a first portion of the trellis and one or
more states in a second portion of the trellis; and
a plurality p of state probability logic modules for determining in parallel
state probabilities for each of p states in either the first or second portions
of the trellis, where p is an integer of two or more, each of the p modules comprising:
first logic for determining for each of one or more branches a branch value,
a branch connecting an originating state with a terminating state, the originating
state having a forward state probability and the terminating state having a backward
state probability, wherein a branch value for a branch is either the sum of the
forward state probability of the originating state of the branch and the branch
metric for the branch or the backward state probability of the terminating state
of the branch and the branch metric for the branch; and
second logic for deriving a state probability for the state corresponding to
the module from a group operation performed on the branch values for one or more branches.
11. A system for determining one or more state probabilities for one or more
states in a trellis representation, the system comprising:
branch metric logic for determining one or more branch metrics for one or more
branches between one or more states in a first portion of the trellis and one or
more states in a second portion of the trellis; and
a plurality p of state probability logic modules for determining in parallel
state probabilities for each of p states in either the first or second portions
of the trellis, where p is an integer of two or more, each of the p modules comprising:
first logic for determining for each of one or more branches a branch value,
a branch value for a branch being derived from one or more state probabilities
and a branch metric for the branch; and
second logic for deriving a state probability for the state corresponding to
the module from a group operation performed on the branch values for one or more branches,
wherein one or more of the state probability logic modules are configured to
concurrently normalize state probabilities of one or more states responsive to
assertion of a normalization control signal.
12. The system of claim 11 further comprising normalization control logic configured
to assert the normalization control signal responsive to an evaluation of selected
bits from the branch values of one or more branches.
13. The system of claim 12 wherein the normalization control logic is configured
to assert the normalization control signal responsive to a comparison of the most
significant bits of the branch values for each of one or more branches between
the first and second portions of the trellis with a predetermined threshold.
14. A system for determining estimates of or extrinsic outputs for one or more
bits using a trellis representation, the trellis representation comprising one
or more branches between one or more states, with one or more of the states having
forward and backward state probabilities, with one or more of the branches having
branch metrics, and with all the branches terminating at a state implying release
of the same value so that the state also implies release of the value, the system comprising:
first logic for deriving a state value for each of one or more states, a state
value for a state being derived from the forward state probability of the state
and the backward state probability of the state;
second logic for deriving a first value by performing a group operation on the
state values for the one or more of the states which imply release of a logical
'1' for a bit;
third logic for deriving a second value by performing a group operation on the
state values for the one or more of the states which imply release of a logical
'0' for the bit; and
fourth logic for deriving an estimate of or extrinsic output for the bit from
the first and second values.
15. The system of claim 14 wherein the fourth logic derives an estimate of the
bit by comparing the first and second values for the bit with a predetermined threshold.
16. The system of claim 14 wherein the group operation is the MAX* operation.
17. The system of claim 14 which is configured to iterate r times, wherein r
is an integer of one or more, for each of r bits.
18. The system of claim 14 wherein the states which imply release of a logical
'1' for the bit are a predetermined first grouping of states, and the states which
imply release of a logical '0' for the bit are a predetermined second grouping
of states.
19. A system for determining an estimate of or extrinsic output for one or more
bits using a trellis representation, the trellis representation comprising one
or more branches between one or more states, with one or more of the states having
forward and backward state probabilities, with one or more of the branches having
branch metrics, and with all the branches terminating at a state implying release
of the same value so that the state also implies release of the value, the system comprising:
first means for deriving a state value for each of one or more states, a state
value for a state being derived from the forward state probability of the state
and the backward state probability of the state;
second means for deriving a first value by performing a group operation on the
state values for one or more of the states which imply release of a logical '1'
for a bit;
third means for deriving a second value by performing a group operation on the
state values for one or more of the states which imply release of a logical '0'
for the bit; and fourth means for deriving an estimate of the bit from the first
and second values.
20. The system of claim 19 wherein the fourth means derives an estimate of a
bit by comparing the difference between the first and second values with a predetermined threshold.
21. A system for determining an estimate of or extrinsic output for one or more
bits using a trellis representation, the trellis representation comprising one
or more branches between one or more branches between one or more states, with
one or more states having forward and backward state probabilities, and one or
more branches having branch metrics, with all the branches connecting a particular
originating and terminating state implying release of the same value, the system comprising:
first logic for determining branch values for each of one or more branches, a
branch value for a branch being derived from one or more state probabilities, and
the branch metric for the branch;
second logic for determining a first value by performing a group operation on
the branch values for the branches which imply release of a logical "1" for the bit;
third logic for determining a second value by performing a group operation on
the branch values for the branches which imply release of a logical "0" for the
bit; and
fourth logic for deriving an estimate or extrinsic output for the bit from the
first and second values.
22. The system of claim 21 wherein the first logic is configured to determine
a branch value for a branch from an a priori probability for the bit.
23. The system of claim 22 wherein the first logic is configured to determine
a branch value for a branch from the sum of the forward state probability of the
originating state of the branch, the backward state probability of the terminating
state of the branch, and the difference between the branch metric for the branch
and the a priori probability for the bit.
24. The system of claim 21 configured to iterate s times, where s is an integer
of one or more, for each of s bits.
25. The system of claim 21 wherein the fourth logic is configured to determine
an extrinsic output for the bit from the difference between the first and second values.
26. A system for determining an estimate of or extrinsic output for one or more
bits using a trellis representation, the trellis representation comprising one
or more branches between one or more branches between one or more states, with
one or more states having forward and backward state probabilities, and one or
more branches having branch metrics, with all the branches connecting a particular
originating and terminating state implying release of the same value, the system comprising:
first means for determining branch values for each of one or more branches, a
branch value for a branch being derived from one or more state probabilities, and
the branch metric for the branch;
second means for determining a first value by performing a group operation on
the branch values for the branches which imply release of a logical "1" for the bit;
third means for determining a second value by performing a group operation on
the branch values for the branches which imply release of a logical "0" for the
bit; and
fourth means for deriving an estimate or extrinsic output for the bit from the
first and second values.
27. A system for computing the MAX* of operands A and B comprising:
first logic for testing the difference A-B relative to zero, and outputting a
signal indicative thereof;
second logic for determining the maximum of the operands A and B, MAX(A,B), by
outputting a signal representative of the operand A if the signal from the first
logic indicates that the difference A-B is greater than zero, and outputting a
signal representative of the operand B otherwise;
third logic for outputting a value corresponding to ln(1+exp(-|A-B|)); and
fourth logic for adding the outputs of the second and third logic, subtracting
a predetermined normalization value responsive to assertion of a normalization
control signal, and outputting a signal indicative thereof.
28. A system for computing the MAX* of operands A and B comprising:
first means for testing the difference A-B relative to zero, and outputting a
signal indicative thereof;
second means for determining the maximum of the operands A and B, MAX(A,B), by
outputting a signal representative of the operand A if the signal from the first
logic indicates that the difference A-B is greater than zero, and outputting a
signal representative of the operand B otherwise;
third means for outputting a value corresponding to ln(1+exp(-|A-B|)); and
fourth means for adding the outputs of the second and third logic, subtracting
a predetermined normalization value responsive to assertion of a normalization
control signal, and outputting a signal indicative thereof.
29. A system for computing one or more state probabilities in a trellis representation
comprising one or more branches between one or more states in a first portion of
the trellis representation and one or more branches in a second portion of the
trellis representation, the system comprising:
branch metric logic for computing one or more branch metrics for one or more
of the branches;
indication logic for indicating whether the system is configured to compute forward
state probabilities or backward state probabilities;
state probability logic for (1) computing one or more forward state probabilities
for one or more states in the second portion of the trellis, while concurrently
normalizing the forward state probabilities responsive to assertion of a normalization
control signal; or (2) computing one or more backward state probabilities of one
or more states in the first portion of the trellis, while concurrently normalizing
the backward state probabilities responsive to assertion of a normalization control signal.
30. The system of claim 29 further comprising estimation logic for computing
estimates of each of r bits, where r is an integer of one or more.
31. The system of claim 30 wherein the estimation logic is activated only when
the system is configured to compute forward state probabilities.
32. The system of claim 29 further comprising extrinsic output logic for computing
an extrinsic output for each of s bits, where s is an integer of one or more.
33. The system of claim 32 wherein the extrinsic output logic is activated only
when the system is configured to compute forward state probabilities.
34. A system for computing one or more state probabilities in a trellis representation
comprising one or more branches between one or more states in a first portion of
the trellis representation and one or more branches in a second portion of the
trellis representation, the system comprising:
branch metric means for computing one or more branch metrics for one or more
of the branches;
indication means for indicating whether the system is configured to compute forward
state probabilities or backward state probabilities;
state probability means for (1) computing one or more forward state probabilities
for one or more states in the second portion of the trellis, while concurrently
normalizing the forward state probabilities responsive to assertion of a normalization
control signal; or (2) computing one or more backward state probabilities for one
or more states in the first portion of the trellis, while concurrently normalizing
the backward state probabilities responsive to assertion of a normalization control signal.
35. The system of claim 34 further comprising estimation means for computing
an estimate of each of r bits, wherein r is an integer of one or more.
36. The system of claim 34 further comprising extrinsic output means for computing
an extrinsic output for each of s bits, where s is an integer of one or more.
37. In decoding logic, a method of determining one or more state probabilities
for one or more states in a trellis representation, the method comprising:
determining one or more branch metrics for one or more branches between one or
more states in a first portion of the trellis and one or more states in a second
portion of the trellis;
determining for each of one or more branches a branch value, a branch connecting
an originating state with a terminating state, the originating state having a forward
state probability and the terminating state having a backward state probability,
wherein a branch value for a branch is either the sum of the forward state probability
of the originating state of the branch and the branch metric for the branch or
the backward state probability of the terminating state of the branch and the branch
metric for the branch; and
deriving a state probability for a state from a group operation performed on
the branch values for one or more branches.
38. The method of claim 37 wherein the group operation is MAX*.
39. The method of claim 37 wherein a forward state probability for a state is
derived from the MAX* of the branch values for each of the branches entering the
state, wherein a branch value for a branch is the sum of the forward state probability
of the originating state of the branch and the branch metric for the branch.
40. The method of claim 37 wherein a backward state probability for a state is
derived from the MAX* of the branch values for each of the branches exiting the
state, wherein a branch value for a branch is the sum of the backward state probability
of the terminating state of the branch and the branch metric for the branch.
41. In decoding logic, a method of determining one or more state probabilities
for one or more states in a trellis representation, the method comprising:
determining one or more branch metrics for one or more branches between one or
more states in a first portion of the trellis and one or more states in a second
portion of the trellis;
determining for each of one or more branches a branch value derived from one
or more state probabilities, and the branch metric for the branch;
deriving a state probability for a state from a group operation performed on
the branch values for one or more branches; and
normalizing the one or more state probabilities responsive to assertion of a
normalization control signal.
42. The method of claim 41 further comprising asserting the normalization control
signal responsive to an examination of selected bits from the branch values of
one or more of the branches.
43. The method of claim 42 further comprising asserting the normalization control
signal responsive to a comparison of the most significant bits of the branch values
with a predetermined threshold.
44. The method of claim 42 further comprising asserting the normalization control
signal responsive to an evaluation of the most significant bits of the branch values
for each of the branches between the first and second portions of the trellis.
45. In decoding logic, a method of determining one or more state probabilities
for one or more states in a trellis representation, the method comprising:
a step for determining one or more branch metrics for one or more branches between
one or more states in a first portion of the trellis and one or more states in
a second portion of the trellis;
a step for deriving a branch value for each of one or more branches, a branch
connecting an originating state with a terminating state, the originating state
having a forward state probability and the terminating state having a backward
state probability, wherein a branch value for a branch is either the sum of the
forward state probability of the originating state of the branch and the branch
metric for the branch or the backward state probability of the terminating state
of the branch and the branch metric for the branch; and
a step for deriving a state probability for each of one or more states, the state
probability for a state being derived from a group operation performed on the branch
values of one or more branches.
46. In decoding logic, a method of determining one or more state probabilities
for states in a trellis representation, the method comprising:
determining one or more branch metrics for one or more branches between one or
more states in a first portion of the trellis and one or more states in a second
portion of the trellis; and
determining in parallel state probabilities for each of p states, where p is
an integer of two or more, by performing the following substeps in parallel for
each of the p states:
determining for each of one or more branches a branch value a branch connecting
an originating state with a terminating state, the originating state having a forward
state probability and the terminating state having a backward state probability,
wherein a branch value for a branch is either the sum of the forward state probability
of the originating state of the branch and the branch metric for the branch or
the backward state probability of the terminating state of the branch and the branch
metric for the branch; and
deriving a state probability for the state from a group operation performed on
the branch values for one or more branches.
47. In decoding logic, a method of determining one or more state probabilities
for one or more states in a trellis representation, the method comprising:
a step for determining one or more branch metrics for one or more branches between
one or more states in a first portion of the trellis and one or more states in
a second portion of the trellis:
a step for deriving a branch value for each of one or more branches, the branch
value for a branch being derived from one or more state probabilities and a branch
metric for the branch;
a step for deriving a state probability for each of one or more states, the state
probability for a state being derived from a group operation performed on the branch
values of one or more branches; and
normalizing the state probabilities for each of the p states responsive to assertion
of a normalization control signal.
48. The method of claim 47 further comprising asserting the normalization control
signal responsive to an examination of selected bits for one or more of branch values.
49. The method of claim 48 further comprising asserting the normalization control
signal responsive to examination of the most significant bits of the one or more
branch values.
50. The method of claim 49 further comprising asserting the normalization control
signal responsive to a comparison of the most significant bits of the branch values
for each of the branches between the first and second portions of the trellis with
a predetermined threshold.
51. In decoding logic, a method of determining an estimate or extrinsic output
of one or more bits from a trellis representation, the trellis representation comprising
one or more branches between one or more states, with one or more of the states
having forward and backward state probabilities, and with one or more of the branches
having branch metrics, with all the branches connecting a particular originating
and terminating state implying release of the same value, the method comprising:
deriving a state value for each of one or more states, the state value for a
state being derived from the forward state probability of the state and the backward
state probability of the state;
deriving a first value by performing a group operation on the state values for
one or more of the states which imply release of a logical '1' for a bit;
deriving a second value by performing a group operation on the state values for
one or more of the states which imply release of a logical '0' for the bit; and
deriving an estimate of or extrinsic output for the bit from the first and second values.
52. The method of claim 51 further comprising deriving an estimate of a bit by
comparing the first and second values with a predetermined threshold.
53. The method of claim 51 wherein the group operation is the MAX* operation.
54. The method of claim 51 further comprising performing r iterations of the
method, wherein r is an integer of one or more, for each of r bits.
55. The method of claim 51 further comprising deriving the first value from a
group operation performed on a predetermined first grouping of one or more states,
and deriving the second value from a group operation performed on a predetermined
second grouping of one or more states.
56. In decoding logic, a method of determining an estimate of or extrinsic output
for one or more bits from a trellis representation, the trellis representation
comprising one or more branches between one or more states, with one or more of
the states having forward and backward state probabilities, and with one or more
of the branches having branch metrics, with all the branches connecting a particular
originating and terminating state implying release of the same value, the method comprising:
a step for deriving a state value for each of one or more states, the state value
for a state being derived from the forward state probability of the state and the
backward state probability of the state;
a step for deriving a first value by performing a group operation on the state
values for one or more states which imply release of a logical '1' for a bit;
a step for deriving a second value by performing a group operation on the state
values for one or more states which imply release of a logical '0' for the bit; and
a step for deriving an estimate of or extrinsic output for the bit from the first
and second values.
57. In decoding logic, a method of determining an estimate of or extrinsic output
for one or more bits using a trellis representation, the trellis representation
comprising one or more branches between one or more branches between one or more
states, with one or more states having forward and backward state probabilities,
and one or more branches having branch metrics, with all the branches connecting
a particular originating and terminating state implying release of the same value,
the method comprising:
determining branch values for each of one or more branches, a branch value for
a branch being derived from one or more state probabilities, and the branch metric
for the branch;
determining a first value by performing a group operation on the branch values
for the branches which imply release of a logical "1" for the bit;
determining a second value by performing a group operation on the branch values
for the branches which imply release of a logical "0" for the bit; and
deriving an estimate or extrinsic output for the bit from the first and second values.
58. The method of claim 57 further comprising determining a branch value for
a branch from an a priori probability for the bit.
59. The method of claim 57 further comprising performing s iterations of the
method, where s is an integer of one or more, for each of s bits.
60. The method of claim 57 further comprising determining a branch value for
a branch from the sum of the forward state probability of the originating state
of the branch, the backward state probability of the terminating state of the branch,
and the difference between the branch metric for the branch and the a priori probability
for the bit.
61. The method of claim 57 further comprising determining an extrinsic output
for the bit from the difference between the first and second values.
62. In decoding logic, a method of determining an estimate of or extrinsic output
for one or more bits using a trellis representation, the trellis representation
comprising one or more branches between one or more branches between one or more
states, with one or more states having forward and backward state probabilities,
and one or more branches having branch metrics, with all the branches connecting
a particular originating and terminating state implying release of the same value,
the method comprising:
a step for determining branch values for each of one or more branches, a branch
value for a branch being derived from one or more state probabilities, and the
branch metric for the branch;
a step for determining a first value by performing a group operation on the branch
values for the branches which imply release of a logical "1" for the bit;
a step for determining a second value by performing a group operation on the
branch values for the branches which imply release of a logical "0" for the bit; and
a step for deriving an estimate or extrinsic output for the bit from the first
and second values.
63. In decoding logic, a method of computing the MAX* of operands A and B comprising:
testing the difference A-B relative to zero, and outputting a signal indicative thereof;
determining the maximum of the operands A and B, MAX(A,B), by outputting a signal
representative of the operand A if the signal resulting from the testing step indicates
that the difference A-B is greater than zero, and outputting a signal representative
of the operand B otherwise;
outputting a value corresponding to ln(1+exp(-|A-B|));
adding the outputs of the second and third steps;
normalizing the sum responsive to assertion of a normalization control signal; and
outputting a signal representative of the normalized sum.
64. In decoding logic, a method of computing state probabilities for each of
one or more states in a trellis representation comprising one or more branches
between one or more states, the method comprising:
computing branch metrics for each of one or more branches;
indicating whether forward or backward operation is desired;
if forward operation is desired, computing forward state probabilities for each
of one or more states, responsive to one or more state probabilities and one or
more branch metrics; and
if backward operation is desired, computing one or more backward state probabilities
of one or more states, responsive to one or more state probabilities and one or
more branches metrics.
65. The method of claim 64 further comprising determining estimates of each of
r bits, where r is an integer of one or more.
66. The method of claim 65 further comprising determining estimates of the r
bits only when forward operation is indicated.
67. The method of claim 64 further comprising determining extrinsic outputs for
each of s bits, where s is an integer of one or more.
68. The method of claim 67 further comprising determining extrinsic outputs for
the s bits only when forward operation is desired.
69. The method of claim 64 further comprising normalizing one or more state probabilities
responsive to assertion of a normalization control signal.
70. In decoding logic, a method of computing one or more state probabilities
in a trellis representation comprising one or more branches between one or more
states, the method comprising:
a step for computing one or more branch metrics for one or more of the branches;
a step for indicating whether forward or backward operation is desired;
a step for computing, if forward operation is desired, one or more forward state
probabilities of one or more states; and
a step for computing, if backward operation is desired, one or more backward
state probabilities of one or more states.
71. The method of claim 70 further comprising a step for determining estimates
of each of r bits, where r is an integer of one or more.
72. The method of claim 71 further comprising a step for determining estimates
of the r bits only when forward operation is desired.
73. The method of claim 70 further comprising a step for determining extrinsic
outputs for each of s bits, where s is an integer of one or more.
74. The method of claim 73 further comprising a step for determining extrinsic
outputs for the s bits only when forward operation is desired.
75. The methods of any of 64, and
70, tangibly embodied as a series of
instructions stored on a processor readable medium.
76. A system comprising a processor and the medium of claim 75.
77. The methods of any of 64, and
70, tangibly embodied as logic.
78. The method of claim 70 further comprising normalizing one or more state probabilities
responsive to assertion of a normalization control signal.
79. In decoding logic, a method of determining one or more state probabilities
for one or more states in a trellis representation, the method comprising:
a step for determining one or more branch metrics for one or more branches between
one or more states in a first portion of the trellis and one or more states in
a second portion of the trellis;
a step for deriving a branch value for each of one or more branches, the branch
value for a branch being derived from one or more state probabilities and a branch
metric for the branch;
a step for deriving a state probability for each of one or more states, the state
probability for a state being derived from a group operation performed on the branch
values of one or more branches; and
a step for normalizing one or more state probabilities responsive to assertion
of a normalization control signal.
Description
FIELD OF THE INVENTION
This invention generally relates to decoders, and, more specifically, to decoders
of trellis codes.
RELATED ART
Trellis codes, such as convolutional codes, or parallel or series combinations
or concatenations of convolutional codes, are codes which are decoded through use
of a trellis. Trellis coded modulation (TCM) codes are groupings of trellis coded
bits which result from mapping the bits into symbols, such as MPSK symbols, prior
to transmission. The symbols may then be used to modulate a carrier, and the modulated
carrier transmitted over a wireline or wireless interface. For additional information
on trellis codes, such as serial or parallel concatenated convolutional codes,
and TCM codes, such as serial concatenated trellis coded modulation codes (SCTCM)
codes, please see U.S. Pat. No. 6,023,783; "Turbo Codes: Analysis, Design, Iterative
Decoding and Applications," Course 909, Part II, International Courses for Telecom
and Semiconductor Professionals, S. Benedetto & D. Divsalar, Oct. 25-29, 1999,
Barcelona, Spain, pp. 324-339; "A Serial Concatenation Approach to Iterative Demodulation
and Decoding," K. Narayanan et al., IEEE Transactions on Communications, Vol. 47,
No. 7, July 1999; "'Turbo DPSK': Iterative Differential PSK Demodulation and Channel
Decoding," P. Hoeher et al., IEEE Transactions on Communications, Vol. 47, No.
6, June 1999; "Serial and Hybrid Concatenated Codes with Applications," D. Divsalar
et al., Proc. Int. Symp. Turbo Codes and Appls., Brest, France, September 1997,
pp. 80-87; "Turbo Trellis Coded Modulation With Iterative Decoding for Mobile Satellite
Communications," D. Divsalar et al., Proc. Int. Mobile Satellite Conf., June 1997;
"Serial Concatenated Trellis Coded Modulation with Iterative Decoding: Design and
Performance," submitted to IEEE Comm. Theory Mini Conference 97 (Globecom 97);
"Near Shannon Limit Error-Correcting Coding: Turbo Codes," C. Berrou et al., Proc.
1993 IEEE International Conference on Communications, Geneva, Switzerland, pp.
1064-1070, May 1993; and "A Soft-Input Soft-Output Maximum A Posteriori (MAP) Module
to Decode Parallel and Serial Concatenated Codes," S. Benedetto, TDA Progress Report
42-127, Nov. 12, 1996, each of which is hereby fully incorporated by reference
herein as though set forth in full.
Decoders of trellis codes may be configured to determine soft or hard estimates
of the underlying source bits or the encoded symbols, or for computing extrinsic
outputs for the underlying source bits or encoded symbols, i.e., soft or hard estimates
with a priori information about the bits or symbols removed. Various forms of decoders
are possible including, for example, maximum a posteriori (MAP) decoders, log-MAP
decoders, MAX-Log-MAP decoders, Viterbi decoders, Soft Output Viterbi (SOVA) decoders,
A Posteriori Probability (APP) decoders, Soft List Viterbi (Soft-LVA) decoders,
etc. For additional information on these decoders, please see "Optimal Decoding
of Linear Codes for Minimizing Symbol Error Rate," L. R. Bahl et al., IEEE Transactions
on Information Theory, March 1974, pp. 27-30; "Near Shannon Limit Error-Correcting
Coding and Decoding: Turbo Codes," C. Berrou et al., Proc. ICC'93 Geneva, Switzerland,
May 1993, pp. 1064-1070; "An Intuitive Justification and a Simplified Implementation
of the MAP Decoder for Convolutional Codes," A. Viterbi, IEEE Journal On Selected
Areas In Telecommunications, Vol. 16, No. 2, February 1998, pp. 260-264; S. Benedetto
et al., "A Soft-Input Soft-Output Maximum A Posteriori (MAP) Module to Decode Parallel
and Serial Concatenated Codes," TDA Progress Report 42-127, Nov. 15, 1996, pp.
1-20; D. Divsalar et al., "Turbo Trellis Coded Modulation with Iterative Decoding
for Mobile Satellite Communications," Proc. Int. Mobile Satellite Conf., June 1997;
"A Comparison of Optimal and Sub-Optimal MAP Decoding Algorithms Operating in the
Log Domain," Proc. IC''95, Seattle, Wash. 1995, pp. 1009-1013; J. Hagenauer & P.
Hoeher, "A Viterbi Algorithm With Soft-Decision Outputs and its applications,"
Proceedings of IEEE GLOBECOM, Dallas, Tex. sec. 47.1.1-47.1.7 (1989); U.S. Pat.
No. 5,181,209; C. Nill & C. E. Sundberg, "List and Soft Symbol Output Viterbi Algorithms:
Extensions and Comparisons," IEEE Transactions on Communications, vol. 43, nos.
2/3/4, pp. 277-87 (February March April 1995); and U.S. Pat. No. 5,537,444, each
of which is hereby fully incorporated by reference herein as though set forth in full.
Known decoders of TCM codes are configured to handle QPSK symbols, but are
susceptible to performance limitations in applications involving MPSK or QAM symbols
beyond QPSK. The problem is particularly acute in applications involving log-MAP
decoders, in which probabilities are expressed in the natural log domain. The computations
needed to perform log-domain calculations places additional demands on the decoders.
<
