Method and apparatus for min star calculations in a map decoder
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
H03D-001/00
H03M-013/03
H03M-013/00
출원번호
US-0952210
(2001-09-12)
발명자
/ 주소
Tran,Hau Thien
Cameron,Kelly B.
Hughes,Thomas A.
출원인 / 주소
Broadcom Corporation
대리인 / 주소
Christie, Parker &
인용정보
피인용 횟수 :
6인용 특허 :
33
초록▼
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 se
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.
대표청구항▼
What is claimed is: 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
What is claimed is: 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. 2. The method of claim 1 wherein determining Min_β comprises: computing A-B to form a difference; and selecting A or B based on the sign bit of the difference. 3. The method of claim 2 wherein selecting A or B based on the sign bit of the result comprises coupling A and B to inputs of a multiplexor; and using the sign bit of the difference to control the multiplexor. 4. The method of claim 2 wherein computing A-B to use in a ln_β calculation is performed essentially simultaneously with computing A and computing B to use in a Min_β calculation. 5. The method of claim 1 wherein computing-log(1+e-|A-B|) begins as soon as any data is available from the A-B calculation without waiting for the A-B calculation to complete. 6. The method of claim 1 wherein computing-log(1+e-|B-A|) begins as soon as any data is available from the A-B calculation without waiting for the A-B calculation to complete. 7. The method as in claim 1 wherein computing ln_β comprises: determining the sign of A-B; and using the result of said determination to compute ln_β. 8. The method as in claim 1 wherein computing ln_β comprises: computing the value of-log(1+e-|A-B|); computing the value of-log(1+e-|B-A|); and selecting the correct value. 9. The method as in claim 1 wherein computing ln_β comprises: computing the value of-log(1+e-|A-B|)+an offset; computing the value of-log(1+e-|B-A|)+an offset; and selecting the correct value. 10. The method of claim 9 wherein the offset is equal to 0.5. 11. The method of claim 8 wherein computing the value of-log(1+e-|A-B|) comprises computing the value of-log(1+e-|A-B|) to an accuracy of 2 bits. 12. The method of claim 8 wherein computing the value of-log(1+e-|B-A|) comprises computing the value of (1+e-|B-A|) to an accuracy of 2 bits. 13. The method of claim 9 wherein computing the value of-log(1+e-|A-B|)+an offset comprises computing the value of-log(1+ e-|A-B|) to an accuracy of 1 bit. 14. The method of claim 9 wherein computing the value of-log(1+e-|B-A|)+an offset comprises computing the value of-log(1+ e-|B-A|) to an accuracy of 1 bit. 15. The method of claim 11 wherein computing the value of-log(1+e-|A-B|) further comprises calculating the log value based on a partial result from the A-B calculation. 16. The method of claim 11 wherein computing the value of-log(1+e-|B-A|) further comprises calculating the log value based on a partial result from the A-B calculation. 17. A method as in claim 15 wherein the partial result comprises a three least significant bits of the A-B calculation. 18. The method of claim 8 wherein computing the value of-log(1+e-|A-B|) is essentially simultaneous with computing the value of-log(1+e-|B-A|). 19. A method as in claim 8 wherein selecting the correct value comprises: determining the sign bit of the A-B calculation; and using the sign bit to select the result of the-log(1+e-|A-B|) or the-log(1+e-|B-A|) calculation. 20. The method as in claim 8 wherein selecting the correct value comprises: determining the third bit of the A-B calculation; using the third bit to select the result of the-log(1+e-|A-B|) or the-log(1+e-|B-A|) calculation; and correcting for an error in selecting the result of the-log(1+ e-|A-B|) or the-log(1+e-|B-A|) calculation. 21. The method as in claim 8 wherein selecting the correct value comprises: determining a bit of the A-B calculation wherein the bit is located between the second bit up to and including the sign bit of the A-B calculation; using the determined bit to select the result of the-log(1+ e-|A-B|) or the-log(1+e-|B-A|) calculation; and correcting for an error in selecting the result of the-log(1+ e-|A-B|) or the-log(1+e-|B-A|) calculation. 22. The method as in claim 20 wherein correcting for an error in selecting the result of the-log(1+e-|A-B|) or the result of the-log(1+e-|B-A|) calculation comprises: computing a value in a log saturation circuit; and combining the value computed in the log saturation circuit with the selected result. 23. The method as in claim 22 wherein combining the value computed in the log saturation circuit with the selected result comprises ORing the value computed in the log saturation circuit with the selected result. 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; and outputting ln_β from the decoder. 25. The decoder of claim 24 wherein determining Min_β comprises: computing A-B to form a difference; and selecting A or B based on the sign bit of the difference. 26. The decoder of claim 25 wherein selecting A or B based on the sign bit of the result comprises: coupling A and B to inputs of a multiplexor; and using the sign bit of the difference to control the multiplexor. 27. The decoder of claim 25 wherein computing A-B to use in a Ln_β calculation is performed essentially simultaneously with computing A and computing B to use in a Min_β calculation. 28. The decoder of claim 24 wherein computing-log(1+e-|A-B|) begins as soon as any data is available from the A-B calculation without waiting for the A-B calculation to complete. 29. The decoder of claim 24 wherein computing-log(1+e-|B-A|) begins as soon as any data is available from the A-B calculation without waiting for the A-B calculation to complete. 30. The decoder of claim 24 wherein computing ln_β comprises: determining the sign of A-B; and using the result of said determination to compute ln_β. 31. The decoder of claim 24 wherein computing ln_β comprises: computing the value of-log(1+e-|A-B|); computing the value of-log(1+e-|B-A|); and selecting the correct value. 32. The decoder of claim 24 wherein computing ln_β comprises: computing the value of-log(1+e-|A-B|)+an offset; computing the value of-log(1+e-|B-A|)+an offset; and selecting the correct value. 33. The decoder of claim 32 wherein the offset is equal to 0. 5. 34. The decoder of claim 31 wherein computing the value of-log(1+e-|A-B|) comprises computing the value of-log(1+e-|A-B|) to an accuracy of 2 bits. 35. The decoder of claim 31 wherein computing the value of-log(1+e-|B-A|) comprises computing the value of (1+e-|B-A|) to an accuracy of 2 bits. 36. The decoder of claim 32 wherein computing the value of-log(1+e-|A-B|)+an offset comprises computing the value of-log(1+ e-|A-B|) to an accuracy of 1 bit. 37. The decoder of claim 32 wherein computing the value of-log(1+e-|B-A|)+an offset comprises computing the value of-log(1+ e-|B-A|) to an accuracy of 1 bit. 38. The decoder of claim 34 wherein computing the value of-log(1+e-|A-B|) further comprises calculating the log value based on a partial result from the A-B population. 39. The decoder of claim 34 wherein computing the value of-log(1+e-|B-A|) further comprises calculating the log value based on a partial result from the A-B population. 40. The decoder of claim 38 wherein the partial result comprises a three least significant bits of the A-B calculation. 41. The decoder of claim 31 wherein computing the value of-log(1+e-|A-B|) is essentially simultaneous with computing the value of-log(1+e-|B-A|). 42. The decoder of claim 31 wherein selecting the correct value comprises: determining the sign bit of the A-B calculation; and using the sign bit to select the result of the-log(1+e-|A-B|) or the-log(1+e-|B-A|) calculation. 43. The decoder of claim 31 wherein selecting the correct value comprises: determining the third bit of the A-B calculation; using the third bit to select the result of the-log(1+e-|A-B|) or the-log(1+e-|B-A|) calculation; and correcting for an error in selecting the result of the-log(1+ e-|A-B|) or the-log(1+e-|B-A|) calculation. 44. The decoder of claim 31 wherein selecting the correct value comprises: determining a bit of the A-B calculation wherein the bit is located between the second bit up to and including the sign bit of the A-B calculation; using the determined bit to select the result of the-log(1+ e-|A-B|) or the-log(1+e-|B-A|) calculation; and correcting for an error in selecting the result of the-log(1+ e-|A-B|) or the-log(1+e-|B-A|) calculation. 45. The decoder of claim 43 wherein correcting for an error in selecting the result of the-log(1+e-|A-B|) or the result of the-log(1+e-|B-A|) calculation comprises: computing a value in a log saturation circuit; and combining the value computed in the log saturation circuit with the selected result. 46. The decoder of claim 45 wherein combining the value computed in the log saturation circuit with the selected result comprises ORing the value computed in the log saturation circuit with the selected result. 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; and a circuit for calculating ln_β=-log(1+e-|A-B|). 48. The apparatus of claim 47 wherein the circuit for calculating the minimum (Min) of A and B comprises: a multiplexor that accepts A as one input and B as a second input; and a circuit that computes A-B and provides the sign bit of the A-B calculation as a control input to the multiplexor. 49. The apparatus of claim 47 wherein the circuit for calculating-log(1+e-|A-B|) comprises: a first circuit that calculates the value of-log(1+e-|A-B|); a second circuit that calculates the value of-log(1+e-|B-A|); and a multiplexor that chooses the calculation of the first circuit or the second circuit. 50. The apparatus of claim 49 wherein the multiplexor is controlled by a bit of the A-B calculation. 51. The apparatus of claim 44 further comprising circuitry that computes A, B, and A-B simultaneously. 52. The apparatus of claim 50 wherein the bit of the A-B calculation is between the third bit of a result from the A-B calculation and a sign bit from the A-B calculation. 53. The apparatus of claim 50 further comprising: an OR gate that receives that accepts a first output from the multiplexor; and a second output that accepts a second output from a log saturation circuit. 54. A method as in claim 1 further comprising simultaneously computing A, B, and AB. 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; and a circuit for calculating ln_β=-log(1+e-|A-B|). 56. The apparatus of claim 55 wherein the circuit for calculating the minimum of A and B comprises: a multiplexor that accepts A as one input and B as a second input; and a circuit that computes A-B and provides the sign bit of the A-B calculation as a control input to the multiplexor. 57. The apparatus of claim 55 wherein the circuit for calculating-log(1+e-|A-B|) comprises: a first circuit that calculates the value of-log(1+e-|A-B|); a second circuit that calculates the value of-log(1+e-|B-A|); and a multiplexor that chooses the calculation of the first circuit or the second circuit. 58. The apparatus of claim 57 wherein the multiplexor is controlled by a bit of the A-B calculation. 59. The apparatus of claim 51 further comprising circuitry that computes A, B, and A-B simultaneously. 60. The apparatus of claim 58 wherein the bit of the A-B calculation is between the third bit of a result from the A-B calculation and a sign bit from the A-B calculation. 61. The apparatus of claim 58 further comprising: an OR gate that accepts a first output from the multiplexor; and a second output that accepts a second output from a log saturation circuit.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (33)
Tsui Chi-ying,HKX ; Cheng Roger Shu Kwan,HKX, Circuit for use in a Viterbi decoder.
Berrou Claude (Le Conquet FRX), Error-correction coding method with at least two systematic convolutional codings in parallel, corresponding iterative d.
Marchetto Robert F. (Burnaby CAX) Stewart Todd A. (West Vancouver CAX) Fawcett Glenn S. (Vancouver CAX), High performance modem using pilot symbols for equalization and frame synchronization.
Van Stralen Nick Andrew ; Ross John Anderson Fergus ; Hladik Stephen Michael ; Itani Abdallah Mahmoud ; Wodnicki Robert Gideon, High-speed turbo decoder.
Hagenauer Joachim,DEX ; Burkert Frank,DEX, Method and arrangement for determining an adaptive abort criterion in iterative decoding of multi-dimensionally coded i.
Bonnot Christophe (Sevres FRX) Gerbault Bertrand (Paris FRX) Seguy Jean-Christophe (Fontenay aux Roses FRX), Method and system for interleaving and deinterleaving SDH frames.
Berrou Claude (le Conquet FRX) Adde Patrick (Brest FRX), Method for a maximum likelihood decoding of a convolutional code with decision weighting, and corresponding decoder.
Pyndiah Ramesh,FRX ; Adde Patrick,FRX, Process for transmitting information bits with error correction coding and decoder for the implementation of this process.
Pyndiah Ramesh,FRX ; Adde Patrick,FRX, Process for transmitting information bits with error correction coding, coder and decoder for the implementation of this process.
Hinedi Sami M. ; Griep Karl R. ; Million Samson, Punctured serial concatenated convolutional coding system and method for low-earth-orbit satellite data communication.
Hladik Stephen Michael ; Check William Alan ; Glinsman Brian James ; Fleming ; III Robert Fleming, Satellite communications system utilizing parallel concatenated coding.
Rajagopal, Sridhar; Shoemake, Matthew B.; Terry, John, Method and apparatus for encoding interleaving and mapping data to facilitate GBPS data rates in wireless systems.
Sarrigeorgidis, Konstantinos; Chen, Yanni; Song, Leilei; Shirali, Kedar, Methods and apparatus for providing a ML decoding pipeline for QPSK MIMO OFDM receivers.
Sarrigeorgidis, Konstantinos; Chen, Yanni; Song, Leilei; Shirali, Kedar, Methods and apparatus for providing a ML decoding pipeline for QPSK MIMO OFDM receivers.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.