• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:
    A perfect integrator emulator includes a first multiplier multiplying an input with a first constant, KNEW, and generating a scaled input, a summer summing the scaled input with a previously generated scaled output and generating an accumulated output, a delay adding a predetermined amount of delay to the accumulated output and generating a delayed output, a second multiplier multiplying the delayed output with a second constant, KOLD, and generating the scaled output. The constants KNEW and KOLD are chosen such that the accumulated output emulates a perfect integrator's relative weighting, and saturation protection is guaranteed.
    公开号:US20010004222A1
    申请号:US09/771,206
    申请日:2001-01-26
    公开日:2001-06-21
    发明作者:David Lupia
    申请人:Lupia David J.；
    IPC主号:G06G7-62
    专利说明:
    [0001] This invention is related in general to the field of digital signal processing, and more particularly, to an anti-saturation integrator and method. [0001] BACKGROUND OF THE INVENTION
    [0002] The Viterbi decoder or the Viterbi decoding algorithm are widely used for efficient coding in digital communication systems. The Viterbi decoder performs maximum likelihood decoding and involves calculating a measure of similarity or distance between the received signal and all the code trellis paths entering each state. The Viterbi algorithm removes trellis paths that are not likely to be candidates for the maximum likelihood choices. Therefore, the Viterbi aims to choose the code word with the maximum likelihood metric or stated another way, the code word with the minimum distance metric. The computation involves accumulating the distance metrics along a path using a perfect integrator. [0002]
    [0003] Referring to FIG. 1, a Viterbi decoder circuit or algorithm portion [0003] 10 includes distance calculators 12-1, 12-2, to 12-N which compute the distance or difference of the received symbol from expected symbols 1 through N. The resultant computed distance from each calculator is then summed with the previous sum. The perfect integrator essentially implements an infinite accumulation for an infinite number of bits. Because a realistic implementation has a finite amount of memory and resources, the resultant accumulated sum inevitably overflows which is a condition know as saturation. When saturation occurs, the solution becomes corrupted and useless. Therefore, it is a requirement of every Viterbi decoder or decoding algorithm to protect against saturation.
    [0004] Conventional anti-saturation solutions check each accumulated sum at each iteration (blocks [0004] 20-1, 20-2, and 20-N) to determine whether the accumulated sum is about to overflow. If yes, the metrics are scaled down by the same value to avoid saturation (blocks 26-1, 26-2, and 26-N). An alternative conventional method involves scaling or normalizing all metrics for every input symbol so that the most likely metric is always zero. Yet a third conventional method uses floating point implementation rather than fixed point implementation.
    [0005] All the above-mentioned anti-saturation techniques suffer from several undesirable disadvantages. These conventional methods slow down the computation speed, use more hardware in the implementation, are more costly, and use more power to operate. Further, the floating point implementation is still at risk for saturation albeit at a decrease rate than the fixed point implementation. [0005] SUMMARY OF THE INVENTION
    [0006] It has been recognized that it is desirable to protect a Viterbi decoder or algorithm from overflow, since such anti-saturation conditions are inevitable in the normal course of operation and would lead to a corrupted output. [0006]
    [0007] In one embodiment of the invention, a perfect integrator emulator includes a first multiplier for multiplying an input with a first constant, K[0007] NEW, and generating a scaled input, a summer for summing the scaled input with a scaled previous output and generating an accumulated output, a delay adding a predetermined amount of delay to the accumulated output and generating a delayed output, a second multiplier for multiplying the delayed output with a second constant, KOLD, and generating the scaled previous output. The constants KNEW and KOLD are chosen such that the accumulated output does not overflow and the integrity of the viterbi decode function is not compromised.
    [0008] In another embodiment of the invention, a method for emulating a perfect integrator includes the steps of multiplying an input with a first constant, K[0008] NEW, and generating a scaled input, summing the scaled input with a previously generated scaled output and generating an accumulated output, adding a predetermined amount of delay to the accumulated output and generating a delayed output, multiplying the delayed output with a second constant, KOLD, and generating the scaled previous output, and whereby the constants KNEW and KOLD are chosen such that the accumulated output does not overflow and the integrity of the viterbi decode function is not compromised.
    [0009] In yet another embodiment of the invention, an anti-saturation Viterbi decoder having an integrator that includes a first multiplier for multiplying a distance input with a first constant, K[0009] NEW, and generating a scaled distance input, a summer for summing the scaled distance input with a scaled previous distance output and generating an accumulated distance output, a delay adding a predetermined amount of delay to the accumulated distance output and generating a delayed distance output, a second multiplier for multiplying the delayed distance output with a second constant, KOLD, and generating the scaled previous distance output. The constants KNEW and KOLD are chosen such that the accumulated distance output does not overflow and the integrity of the viterbi decode function is not compromised. BRIEF DESCRIPTION OF THE DRAWINGS
    [0010] For a better understanding of the present invention, reference may be made to the accompanying drawings, in which: [0010]
    [0011] FIG. 1 is a simplified block diagram of a conventional portion of a Viterbi decoder including an integrator used for matched distance decay accumulation; [0011]
    [0012] FIG. 2 is a block diagram of a perfect integrator emulator used for matched distance decay accumulation according to the teachings of the present invention; [0012]
    [0013] FIG. 3 is a distance delay plot comparing a perfect integrator with the perfect integrator emulator of the present invention using specific K[0013] NEW and KOLD values; and
    [0014] FIG. 4 is a theoretical bit rate error (BER) curve plot comparing a perfect integrator and emulated perfect integrator using various specific K[0014] NEW and KOLD values. DETAILED DESCRIPTION OF THE INVENTION
    [0015] FIG. 2 is a block diagram of a perfect integrator emulator [0015] 40 used for matched distance decay accumulation according to the teachings of the present invention. Perfect integrator emulator 40 strives to emulate the properties of a perfect integrator. Perfect integrator emulator 40 receives as input the distance calculated between the received symbol and an expected symbol. The distance input is first multiplied with a first predetermined scaling constant, KNEW, by a first multiplier 42 and the resultant product is a scaled distance value 43, which is provided to a summer 42. Summer 42 sums scaled distance value 43 with a scaled old or previous distance value 45 from the output of a second multiplier 48. Second multiplier 48 multiplies a second predetermined scaling constant, KOLD, with the previous distance 49 from the output of a delay circuit 46. The input to delay circuit 46 is the new distance or the accumulated distance 52.
    [0016] According to the teachings of the present invention, the new distance sum may be computed by: [0016] NEW    [ N ] =( N N + 1 )     OLD + ( 1 N + 1 )     DISTANCE
    [0017] The constants (N/N+1) and (1/N+1) preferably describe the function of the perfect integrator. The perfect integrator weighs the old and distance values for each successive iteration. The weighting of each component may be described individually: [0017] OLD    [ N ] = ( N N + 1 )     OLD DISTANCE    [ N ]    = ( 1 N + 1 )     DISTANCE
    [0018] Therefore the key to the distance decay anti-saturation function is that the K[0018] NEW and KOLD constants are selected such that the overall effect emulates a perfect integrator's relative weighting. It is shown below that the invention contemplates KNEW=0.01 and KOLD=0.99, which allows circuit 40 shown in FIG. 2 to emulate a perfect integrator. With carefully chosen scalar constant values such as KNEW=0.01 and KOLD=0.99, saturation will not occur and a perfect integrator's relative weighting is still emulated.
    [0019] FIG. 3 is a distance decay plot comparing a perfect integrator with the emulated perfect integrator of the present invention using specific K[0019] NEW and KOLD values. It may be seen that with KNEW=0.01 and KOLD=0.99 (curve marked with □ symbol), circuit or algorithm 40 most closely emulates a perfect integrator (curve marked with Δ symbol). The third curve uses KNEW=0.1 and KOLD=0.9 (curve marked with ⋄ symbol), which yields an undesirable result far different from the perfect integrator.
    [0020] FIG. 4 is a theoretical bit rate error (BER) curve plot comparing a perfect integrator (curve marked with x) and integrators using various specific K[0020] NEW and KOLD values. This plot shows how significant degradation occurs for improperly chosen KNEW and KOLD constants. It may be seen that for KNEW=0.01 and KOLD=0.99 (curve marked with Δ symbol), with symbol-noise distance, there is very little degradation when compared with the perfect integrator's floating point implementation. However, for constant pairs (KNEW,KOLD)= (0.1, 0.9), (0.2, 0.8), and (0.99, 0.01) (curves with *, , and ♦ respectively), very significant degradation is observed. Degradation at this scale indicates a virtually non-functioning Viterbi decoder and algorithm.
    [0021] The foregoing illustrates the importance that K[0021] NEW and KOLD constants be carefully selected such that the effect on the distance decay emulates the perfect integrator's distance decay curve. Employing the present invention, a Viterbi decoder or algorithm is now protected from saturation.
    [0022] Although several embodiments of the present invention and its advantages have been described in detail, it should be understood that mutations, changes, substitutions, transformations, modifications, variations, and alterations can be made therein without departing from the teachings of the present invention, the spirit and scope of the invention being set forth by the appended claims. [0022]
    权利要求:
    Claims (11)
    [1" id="US-20010004222-A1-CLM-00001] 1. A perfect integrator emulator, comprising:
    a first multiplier for multiplying an input with a first constant, KNEW, and generating a scaled input;
    a summer for summing the scaled input with a previously generated scaled output and generating an accumulated output;
    a delay adding a predetermined amount of delay to the accumulated output and generating a delayed output;
    a second multiplier for multiplying the delayed output with a second constant, KOLD, and generating the scaled output; and
    whereby the constants KNEW and KOLD are chosen such that the accumulated output does not overflow or underflow.
    [2" id="US-20010004222-A1-CLM-00002] 2. The perfect integrator emulator, as set forth in
    claim 1 , wherein KNEW is 0.01 and KOLD is 0.99.
    [3" id="US-20010004222-A1-CLM-00003] 3. The perfect integrator emulator, as set forth in
    claim 1 , wherein the input represents a difference between the value of a signal and the value of an expected signal.
    [4" id="US-20010004222-A1-CLM-00004] 4. The perfect integrator emulator, as set forth in
    claim 1 , wherein the accumulated output represents an accumulated distance metric employed in a Viterbi decoder.
    [5" id="US-20010004222-A1-CLM-00005] 5. A method for emulating a perfect integrator, comprising:
    multiplying an input with a first constant, KNEW, and generating a scaled input;
    summing the scaled input with a previously generated scaled output and generating an accumulated output;
    adding a predetermined amount of delay to the accumulated output and generating a delayed output;
    multiplying the delayed output with a second constant, KOLD, and generating the scaled output; and
    whereby the constants KNEW and KOLD are chosen such that the accumulated output does not overflow or underflow.
    [6" id="US-20010004222-A1-CLM-00006] 6. The method, as set forth in
    claim 5 , wherein the multiplying comprises utilizing KNEW equal to 0.01 and KOLD equal to 0.99.
    [7" id="US-20010004222-A1-CLM-00007] 7. The method, as set forth in
    claim 5 , wherein multiplying the input comprises multiplying a difference between the value of a signal and the value of an expected signal with the first constant KNEW.
    [8" id="US-20010004222-A1-CLM-00008] 8. The method, as set forth in
    claim 5 , wherein summing the scaled input with a previously generated scaled output comprises accumulating a distance metric employed in a Viterbi decoder.
    [9" id="US-20010004222-A1-CLM-00009] 9. An anti-saturation Viterbi decoder, comprising:
    a first multiplier for multiplying a distance input with a first constant, KNEW, and generating a scaled distance input;
    a summer for summing the scaled distance input with a previously generated scaled distance output and generating an accumulated distance output;
    a delay adding a predetermined amount of delay to the accumulated distance output and generating a delayed distance output;
    a second multiplier for multiplying the delayed distance output with a second constant, KOLD, and generating the scaled previous distance output; and
    whereby the constants KNEW and KOLD are chosen such that the accumulated distance output does not overflow or underflow.
    [10" id="US-20010004222-A1-CLM-00010] 10. The Viterbi decoder, as set forth in
    claim 9 , wherein KNEW equals 0.01 and KOLD equals 0.99.
    [11" id="US-20010004222-A1-CLM-00011] 11. The Viterbi decoder, as set forth in
    claim 9 , wherein the distance input represents a distance between the value of a signal and the value of an expected signal.
    类似技术:
    公开号 | 公开日 | 专利标题
    US6631172B1|2003-10-07|Efficient list decoding of Reed-Solomon codes for message recovery in the presence of high noise levels
    US6637002B1|2003-10-21|Decoder for error correcting block codes
    US8458574B2|2013-06-04|Compact chien-search based decoding apparatus and method
    US8086928B2|2011-12-27|Methods and systems for terminating an iterative decoding process of a forward error correction block
    CN100547935C|2009-10-07|Decoding device and coding/decoding method
    US7391826B2|2008-06-24|Decoding method and apparatus
    EP0671817A1|1995-09-13|Soft symbol decoding for use in an MLSE-equaliser or convolutional decoder
    JP2005065271A5|2005-07-07|
    JPH0936755A|1997-02-07|Decoder and its method
    CN100380816C|2008-04-09|Soft demodulation method and apparatus
    RU2344556C1|2009-01-20|Decoder with correction of deletions
    EP1700380B1|2007-03-28|Turbo decoding with iterative estimation of channel parameters
    Ahmed et al.2004|VLSI architectures for soft-decision decoding of Reed-Solomon codes
    US20030046637A1|2003-03-06|Even-load software reed-solomon decoder
    US6265927B1|2001-07-24|Anti-saturation integrator and method
    US6915478B2|2005-07-05|Method and apparatus for computing Reed-Solomon error magnitudes
    US6377618B1|2002-04-23|Auto-correlation system and method for rate detection of a data communication channel
    US6614858B1|2003-09-02|Limiting range of extrinsic information for iterative decoding
    US6760883B2|2004-07-06|Generating log-likelihood values in a maximum a posteriori processor
    US6421807B1|2002-07-16|Decoding apparatus, processing apparatus and methods therefor
    US7197526B1|2007-03-27|Method and apparatus for calculating the remainder of a modulo division
    US9542262B1|2017-01-10|Error correction
    US7055102B2|2006-05-30|Turbo decoder using parallel processing
    RU2236090C1|2004-09-10|Communication channel quality control process
    RU165283U1|2016-10-10|DEVICE PROBABILITY EVALUATION DEVICE FOR BIT IN BIT STREAM, CODED WITH WIRELESS CODE
    同族专利:
    公开号 | 公开日
    US6359495B2|2002-03-19|
    US6265927B1|2001-07-24|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    US11055121B1|2020-01-30|2021-07-06|Bank Of America Corporation|Computer architecture for emulating an integrator in a correlithm object processing system|US5173924A|1990-05-21|1992-12-22|Sony Corporation|Method for equalizing received burst signal|
    JPH08307283A|1995-03-09|1996-11-22|Oki Electric Ind Co Ltd|Device and method for estimating maximum likelihood series|
    US5619154A|1995-10-10|1997-04-08|David Sarnoff Research Center, Inc.|Numerical voltage controlled oscillator|US9876490B2|2012-11-20|2018-01-23|The Trustees Of Columbia University In The City Of New York|Systems, apparatus, and methods for providing continuous-time signal differentiation and integration|
    US20140139280A1|2012-11-20|2014-05-22|The Trustees Of Columbia University In The City Of New York|Systems, apparatus, and methods for providing continuous-time signal differentiation and integration|
    法律状态:
    2002-03-01| STCF| Information on status: patent grant|Free format text: PATENTED CASE |
    2002-07-23| CC| Certificate of correction|
    2005-08-18| FPAY| Fee payment|Year of fee payment: 4 |
    2009-09-14| FPAY| Fee payment|Year of fee payment: 8 |
    2013-08-21| FPAY| Fee payment|Year of fee payment: 12 |
    优先权:
    申请号 | 申请日 | 专利标题
    US09/434,704|US6265927B1|1999-11-05|1999-11-05|Anti-saturation integrator and method|
    US09/771,206|US6359495B2|1999-11-05|2001-01-26|Anti-saturation integrator and method|US09/771,206| US6359495B2|1999-11-05|2001-01-26|Anti-saturation integrator and method|
    [返回顶部]