Method and apparatus for min star calculations in a map decoder
First Claim
Patent Images
1. A method performed by a decoder for computing Min star of a first input (A) and a second input (B) to the decoder (Min*(A, B)), the method comprising:
- determining Min_β
=minimum of the operands comparing the first input (A) and the second input (B) to the decoder, wherein A comprises an β
metric, a priori values and a transition metric for a first previous state of the decoder and B comprises an β
metric, a priori values and a transition metric for a second previous state of the decoder;
outputting Min_β
, wherein Min_β
comprises the Minimum of A and B, a first portion of the output of the Min* operation;
computing ln_β
=−
log(1+e−
|A−
B|) as a second portion of the Min* operation; and
outputting ln_β
from the decoder.
3 Assignments
0 Petitions
Accused Products
Abstract
Method and apparatus for Min star calculations in a Map decoder. Min star calculations are performed by a circuit that includes a first circuit that performs an Min(A,B) operation simultaneously with a circuit that calculates a −log(1+e−|A−B|) value. The sign bit of the A−B calculation is used to select whether A or B is a minimum. The A−B calculation is also used to select either −log(1+e−|A−B|) or −log(1+e−|B−A|) as the correct calculation. In order to hasten the selection of either −log(1+e−|A−B|) or −log(1+e−|B−A|) as the correct calculation the apparatus does not wait for the A−B calculation to complete. Any bit of the A−B calculation between the third bit and final (sign bit) can be used for the selection. If an incorrect value is selected a log saturation circuit may correct the value. In addition an offset may be added −log(1+e−|A−B|) or −log(1+e−|B−A|) to assure that the calculation does not become negative, necessitating the use of an additional sign bit thereby increasing circuit complexity and slowing down the calculation. Additionally the log terms are computed based on a partial result of the A−B calculation.
47 Citations
61 Claims
-
1. A method performed by a decoder for computing Min star of a first input (A) and a second input (B) to the decoder (Min*(A, B)), the method comprising:
-
determining Min_β
=minimum of the operands comparing the first input (A) and the second input (B) to the decoder, wherein A comprises an β
metric, a priori values and a transition metric for a first previous state of the decoder and B comprises an β
metric, a priori values and a transition metric for a second previous state of the decoder;outputting Min_β
, wherein Min_β
comprises the Minimum of A and B, a first portion of the output of the Min* operation;computing ln_β
=−
log(1+e−
|A−
B|) as a second portion of the Min* operation; andoutputting ln_β
from the decoder. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 54)
-
-
24. A map decoder embodying a program of instructions executable by the map decoder to compute a beta metric for a selected state of the decoder, the program of instructions when executed by the map decoder perform the steps of:
-
determining Min_β
=minimum of the operands comparing a first input (A) and a second input (B) to the decoder, wherein A comprises a β
metric, a priori values and a transition metric for a first next state of the decoder and B comprises an β
metric, a priori values and a transition metric for a second next state of the decoder;outputting Min_β
from the Min* operation wherein Min_β
comprises the minimum of A and B, a first portion of the output of a Min* operation;computing ln_β
=−
log(1+e−
|A−
B|as a second portion of a Min* operation; andoutputting ln_β
from the decoder. - View Dependent Claims (25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 51, 59)
-
-
47. An apparatus for calculating a Min*(A, B) in a MAP decoder the apparatus comprising:
-
a circuit for calculating the minimum (Min) of A and B where A is the sum of a1 and a2 and a3, wherein a1 is the Min_β
of a first previous state, a2 is ln_β
of the previous state and a3 is equal to a priori values from the first previous state plus a transition metric from the first previous state and B is equal to b1 and b2 and b3, wherein b1 is the Min_β
of a second previous state, b2 is ln_β
of the second previous state and b3 is equal to a priori values from the second previous state plus a transition metric from a previous state, wherein Min β
comprises the Min (A, B) for a given state; anda circuit for calculating ln_β
=−
log(1+e−
|A−
B|). - View Dependent Claims (48, 49, 50, 52, 53)
-
-
55. An apparatus for calculating a Min*(A, B) in a MAP decoder the apparatus comprising:
-
a circuit for calculating the minimum (Min) of A and B where A is the sum of a1 and a2 and a3, wherein a1 is the Min_β
of a first next state, a2 is ln_β
of the first next state and a3 is equal to a priori values from the first next state plus a transition metric into the first next state and B is equal to b1 and b2 and b3, wherein b1 is the Min_β
of a second next state, b2 is ln_β
of the second next state and b3 is equal to a priori values into the second next state plus a transition metric into the second next state, wherein Min_β
comprises the Min (A, B) for a given state; anda circuit for calculating ln_β
=−
log(1+e−
|A−
B|). - View Dependent Claims (56, 57, 58, 60, 61)
-
Specification
-
- Resources
Litigation Campaign Assessment
Thank you for your request. You will receive a custom alert email when the Litigation Campaign Assessment is available.
×
-
Current AssigneeBroadcom Corporation (Broadcom, Inc.)
-
Original AssigneeBroadcom Corporation (Broadcom, Inc.)
-
InventorsTran, Hau Thien, Cameron, Kelly B., Hughes, Thomas A.
-
Primary Examiner(s)Vanderpuye, Kenneth
-
Assistant Examiner(s)WILLIAMS, LAWRENCE B
-
Application NumberUS09/952,210Publication NumberTime in Patent Office1,665 DaysField of Search375/265, 375/340, 375/341, 375/262, 714/755, 714/792, 714/795, 714/780, 714/786, 714/794, 714/796US Class Current375/341CPC Class CodesH03M 13/151 using error location or err...H03M 13/1515 Reed-Solomon codesH03M 13/25 Error detection or forward ...H03M 13/258 with turbo codes, e.g. Turb...H03M 13/27 using interleaving techniquesH03M 13/2757 Interleaver with an interle...H03M 13/29 combining two or more codes...H03M 13/2966 Turbo codes concatenated wi...H03M 13/2978 Particular arrangement of t...H03M 13/3905 Maximum a posteriori probab...H03M 13/3922 Add-Compare-Select [ACS] op...H03M 13/3927 Log-Likelihood Ratio [LLR] ...H03M 13/3972 using sliding window techni...H03M 13/3988 for rate k/n convolutional ...H03M 13/4107 implementing add, compare, ...H03M 13/6505 Memory efficient implementa...H03M 13/6561 Parallelized implementationsH04L 1/0041 Arrangements at the transmi...H04L 1/005 Iterative decoding, includi...H04L 1/006 Trellis-coded modulationView All
