Efficient iterative decoding

Apparatus for iterative decoding of a sequence of signal packets coded in accordance with a multi-component coding scheme. The apparatus includes a plurality of decoders, each of which performs a respective different decoding method on one of the signal packets, such that the plurality of decoders operate substantially concurrently. Iterative decoding may be stopped if a predefined threshold maximum number of iterations is reached, or if the previous two decoder iterations have satisfactory cyclic redundancy checks (CRC), or if the input frame buffer to the decoder is filled to within a predefined percentage of its storage capacity.

FIELD OF THE INVENTION
 The present invention relates generally to iterative decoding, and
 specifically to fast iterative decoding of multiple-component codes.
 BACKGROUND OF THE INVENTION
 Transmission of digital data is inherently prone to interference which may
 introduce errors into the transmitted data. Error detection schemes have
 been suggested to determine as reliably as possible whether errors have
 been introduced into the transmitted data. For example, it is common to
 transmit the data in packets, and add to each packet a CRC (cyclic
 redundancy check) field, for example of a length of 16 bits, which carries
 a checksum of the data of the packet. When a receiver receives the data,
 it calculates the same checksum on the received data and verifies whether
 the result of its calculation is identical to the checksum in the CRC
 field.
 When the transmitted data is not used on-line, it is possible to request
 re-transmission of erroneous data when errors are detected. However, when
 the transmission is performed on-line such as in telephone lines, cellular
 phones, remote video systems, etc., it is not possible to request
 re-transmission.
 Convolution codes have been introduced to allow receivers of digital data
 to correctly determine the transmitted data even when errors may have
 occurred during transmission. The convolution codes introduce redundancy
 into the transmitted data and pack the transmitted data into packets in
 which the value of each bit is dependent on earlier bits in the sequence.
 Thus, when a few errors occur, the receiver can still deduce the original
 data by tracing back possible sequences in the received data.
 To further improve the performance of a transmission channel, some coding
 schemes include interleavers, which mix up the order of the bits in the
 packet during coding. Thus, when interference destroys a few adjacent bits
 during transmission, the effect of the interference is spread out over the
 entire original packet and can more readily be overcome by the decoding
 process. Other improvements may include multiple-component codes which
 include coding the packet more than once in parallel or in series. For
 example, U.S. Pat. No. 5,446,747, which is incorporated herein by
 reference, describes an error correction method using at least two
 convolutional codings in parallel. Such parallel encoding is known in the
 art as "Turbo coding."
 For multiple component codes, optimal decoding is often a very complex
 task, and may require large periods of time, not usually available for
 on-line decoding. In order to overcome this problem, iterative decoding
 techniques have been developed. Rather than determining immediately
 whether received bits are zero or one, the receiver assigns each bit a
 value on a multi-level scale representative of the probability that the
 bit is one. A common scale, referred to as LLR probabilities, represents
 each bit by an integer in the range {-32,31}. The value of 31 signifies
 that the transmitted bit was a zero with very high probability, and the
 value of -32 signifies that the transmitted bit was a one, with very high
 probability. A value of zero indicates that the value is indeterminate.
 Data represented on the multi-level scale is referred to as "soft data,"
 and iterative decoding is usually soft-in/soft-out, i.e., the decoding
 process receives a sequence of inputs corresponding to probabilities for
 the bit values and provides as output corrected probabilities taking into
 account constraints of the code. Generally, a decoder which performs
 iterative decoding, uses soft data from former iterations to decode the
 soft data read by the receiver. A method of iterative decoding is
 described, for example, in U.S. Pat. No. 5,563,897, which is incorporated
 herein by reference.
 During iterative decoding of multiple-component codes, the decoder uses
 results from decoding of one code to improve the decoding of the second
 code. When parallel encoders are used, as in Turbo coding, two
 corresponding decoders may conveniently be used in parallel for this
 purpose.
 The iterative decoding is carried out for a plurality of iterations until
 it is believed that the soft data closely represents the transmitted data.
 Those bits which have a probability indicating that they are closer to one
 (for example, between 0 and 31 on the scale described above) are assigned
 binary zero, and the rest of the bits are assigned binary one.
 Generally, the iterative process is repeated a predetermined number of
 times. According to "An Introduction to Turbo Codes," by Matthew C.
 Valenti, which can be found at
 &lt;&lt;http://lamarr.mprg.ee.vt.edu/documents/turbo.pdf&gt;&gt;, and is incorporated
 herein by reference, the predetermined number of iterations is about 18.
 However, this article further states that in many cases as few as 6
 iterations can provide satisfactory performance. "Iterative Decoding of
 Binary Block Codes," by Joachim Hagenauer, Elke Offer and Lutz Papke, IEEE
 Trans. of Information Theory, Vol. 42, No. 2, pp. 429-445 (March 1996),
 which is incorporated herein by reference, suggests using a cross entropy
 criteria to determine when to stop the iterative decoding process
 individually for each packet. Thus, the calculation power of a decoder may
 be used more efficiently than when all packets are decoded using the same
 number of iterations. However, the cross entropy criterion is in itself
 very complex, reducing substantially the gain in efficiency in applying
 variable numbers of iterations.
 In one commonly-used multiple-component coding scheme, the packet is first
 encoded by a first "outer" coding scheme. Thereafter, it is interleaved
 and is then encoded by a second "inner" coding scheme. During decoding,
 the inner code is first decoded, the result is de-interleaved, and then
 the outer code is decoded. The results of decoding the outer code are
 thereafter used in a second iteration of decoding the inner code to
 improve its results. This process is continued iteratively until the coded
 packet is satisfactorily decoded.
 The above-described decoding scheme is typically implemented by a single
 hardware decoder, which alternately decodes the inner and outer codes.
 However, when very fast decoding is needed, and the inner and outer codes
 are substantially different, the computational load is generally beyond
 the capability of a single decoder of conventional design. Therefore, it
 has been suggested to use a decoder including two processors, one for the
 inner code and one for the outer code. However, this results in having
 each of the processors idle half of the time, while it waits for results
 from the other processor.
 SUMMARY OF THE INVENTION
 It is an object of some aspects of the present invention to provide methods
 and apparatus for fast iterative decoding of codes based on two or more
 different convolutional encoding schemes.
 It is another object of some aspects of the present invention to provide
 apparatus for efficient iterative decoding of convolution codes.
 It is a further object of some aspects of the present invention to provide
 an efficient method for determining how many iterations are needed for
 reliable decoding of a packet.
 In exemplary embodiments of the present invention, the decoding time
 allotted for decoding each code in a multi-code series or parallel coding
 scheme is made substantially equal. A decoder including two processors
 receives two packets of data in sequence and decodes them simultaneously.
 While one packet is being decoded in a first processor, the second
 processor decodes the second packet. When both processors finish a single
 iteration, the packets are switched between the processors, and another
 iteration is performed. Thus, both processors are substantially constantly
 in use, and codes may be decoded twice as fast as in prior art schemes of
 comparable hardware complexity. Preferably, both processors operate
 concurrently at least 50% of their operation time on any input packet.
 In some embodiments of the present invention, the two packets are decoded
 independently of each other, so that termination of decoding of the
 packets is independent. When a first packet is finished being decoded, a
 new packet may enter one of the decoders, regardless of whether the second
 packet has finished being decoded.
 In some embodiments of the present invention, the multi-code scheme
 includes an inner coding scheme and an outer coding scheme. Preferably,
 the inner and outer coding schemes are chosen such that the decoding time
 of a single iteration of both of them is approximately the same.
 Alternatively or additionally, the processor that finishes an iteration
 first waits for the second processor to finish processing, and then the
 packets are switched between the decoders. Preferably, the inner and outer
 coding schemes are different and cannot easily be decoded by the same
 processor.
 In another aspect of the present invention, during decoding of each packet,
 a simple method is used for determining when to stop the iterative
 process. A termination checking procedure is preferably performed after
 each iteration, and includes determining a minimal absolute probability
 value associated with any of the bits in the packet. When the minimal
 absolute probability value is above a predetermined threshold, indicating
 that all of the bits have been assigned either the value "1" or "0" with
 relatively high probability, the iterative process is terminated.
 Alternatively or additionally, each packet is transmitted with a CRC field.
 After each decoding iteration, the termination checking procedure checks
 whether the CRC value computed from the data to be output from that
 iteration is compatible with the CRC field. Preferably, the checking
 procedure checks the CRC field only when the minimal probability value is
 above the threshold. If the CRC field is compatible with the extracted
 data, the iteration procedure is terminated.
 In some embodiments of the present invention, the checking procedure is
 begun only after a minimal initial number of iterations, in order to
 reduce the probability of the CRC check returning an apparently "correct"
 result although the decoded data is incorrect. Preferably, the minimal
 number of iterations is between four and eight. The number of iterations
 is preferably chosen to be a number of iterations which for most packets
 does not bring the minimal probability value above the threshold. Further
 preferably, the iterative process is terminated after a maximal number of
 iterations regardless of any other conditions. Preferably, the maximal
 number of iterations is between 20 and 30.
 In other embodiments of the present invention, the minimal absolute
 probability value may be replaced by an average probability value, by a
 median probability value, or by any other value indicative of the progress
 of the iterative decoding process. For example, when it is desired to
 minimize a bit error (BER) criterion rather than a packet error rate, the
 minimal absolute value is preferably replaced by a next-to-minimum value,
 i.e., the lowest value after ignoring one or two exceptions.
 There is therefore provided in accordance with one embodiment of the
 present invention, apparatus for iterative decoding of a sequence of
 signal packets coded in accordance with a multi-component coding scheme,
 including a plurality of decoders, each of which performs a respective
 different decoding method on one of the signal packets, such that the
 plurality of decoders operate substantially concurrently.
 Preferably, the plurality of decoders operate concurrently on different,
 respective packets.
 Preferably, the plurality of decoders operate concurrently during at least
 50% of the operation time during which the apparatus decodes the sequence.
 Further preferably, the plurality of decoders operate concurrently during
 substantially the entire operation time of the apparatus.
 Preferably, each of the plurality of decoders receives as its input a
 packet processed by another one of the plurality of decoders in most of
 the iterations.
 Preferably, the plurality of decoders includes two decoders.
 Preferably, the apparatus further includes a plurality of memory units to
 which the decoders output the packets after decoding.
 Preferably, the packets are interleaved or de-interleaved after decoding.
 Preferably, each of the plurality of decoders requires a generally equal
 decoding time to that of the other decoders.
 Preferably, the multi-component coding scheme includes a parallel coding
 scheme.
 Alternatively, the multi-component coding scheme includes a serial coding
 scheme.
 Preferably, the plurality of decoders include APP decoders.
 There is further provided in accordance with another embodiment of the
 present invention, a method of decoding a sequence of packets of data,
 coded in accordance with a multi-component coding scheme including inner
 and outer codes, including decoding a first packet in a first decoder,
 which decodes the inner code to generate a first decoded output packet,
 and decoding the first decoded output packet in a second decoder, which
 decodes the outer code, while substantially concurrently decoding a second
 packet in the first decoder.
 Preferably, the method includes outputting the first packet from the second
 decoder to the first decoder, so as to repeat decoding the inner code.
 Preferably, the method includes repeatedly decoding the first and second
 packets in the first and second decoders in alternation.
 Preferably, the method includes de-interleaving the first output packet
 before decoding it in the second decoder.
 Preferably, the multi-component coding scheme includes a serial-coding
 scheme.
 There is further provided in accordance with another embodiment of the
 present invention, in a system for iterative decoding of a packet of soft
 data in which each bit is represented by a probability value, a method for
 determining after which of a plurality of iterations to terminate the
 decoding, including determining a probability value of the bits in the
 packet, and deciding to terminate the decoding only if the probability
 value is above a predetermined value.
 Preferably, determining the probability value includes determining a
 minimal probability of the hard data values of the bits in the packet.
 Preferably, determining the minimal probability value includes determining
 a minimal absolute log probability value.
 Preferably, the method includes verifying that an error detection field in
 the packet is correct, and deciding to terminate includes deciding to
 terminate only if the error detection field is correct.
 Preferably, verifying that the error detection field is correct is
 performed when the probability value is above the predetermined value.
 Preferably, determining the probability value is performed only after a
 predetermined number of decoding iterations performed on the packet.
 Preferably, determining the probability value includes determining the
 probability value on a decoded copy of the bits in the packet.
 Alternatively or additionally, determining the probability value includes
 determining the probability value on a coded copy of the bits in the
 packet.
 There is further provided in accordance with another embodiment of the
 present invention, apparatus for iterative decoding of coded packets
 including for each bit a probability value, including a decoder which
 performs iterations of decoding the packet, and a control unit which
 determines whether an additional iteration is to be performed by the
 decoder responsive to the probability values of the bits in the packet.
 Preferably, the control unit causes the decoder to perform a predetermined
 number of iterations without checking the packet.
 Preferably, the control unit determines whether an additional iteration is
 to be performed by the decoder responsive to an error detection field in
 the packet if the probability values fulfill a predetermined condition.
 Preferably, the control unit does not initiate an additional iteration by
 the decoder if the error detection field is correct.
 Preferably, the decoder includes an APP decoder.
 Preferably, the control unit calculates a minimal probability of the hard
 data values of the bits in the packet and determines whether an additional
 iteration is to be performed responsive to the minimal probability.
 Further preferably, the control unit calculates a minimal absolute log
 probability value.
 Preferably, the control unit calculates the minimal probability based on a
 probability value of either a decoded or coded copy of the packet.
 In accordance with one aspect of the present invention, there is
 advantageously further provided a method of terminating an iterative
 decoding process being performed on a packet in an iterative decoder,
 comprising the steps of determining whether a number of decoding
 iterations equals a predefined maximum number of iterations; determining
 whether a packet storage element coupled to an input of the iterative
 decoder is filled to within a predefined percentage of the storage
 capacity of the packet storage element; determining whether the number of
 decoding iterations equals a predefined minimum number of iterations;
 determining whether an error-detection measure has been satisfied for at
 least one previous packet; and terminating the iterative decoding process
 for the packet if (1) the number of decoding iterations equals the
 predefined maximum number of iterations, or if (2) the packet storage
 element is filled to within the predefined percentage of the storage
 capacity of the packet storage element, or if (3) the number of decoding
 iterations equals the predefined minimum number of iterations, and the
 error-detection measure has been satisfied for the at least one previous
 packet.
 In accordance with another aspect of the present invention, there is
 advantageously further provided an iterative decoder, comprising first and
 second decoding means for performing an iterative decoding process on a
 packet; packet storage means coupled to the first and second decoding
 means; means for determining whether a number of decoding iterations
 equals a predefined maximum number of iterations; means for determining
 whether the packet storage means is filled to within a predefined
 percentage of the storage capacity of the packet storage means; means for
 determining whether the number of decoding iterations equals a predefined
 minimum number of iterations; means for determining whether an
 error-detection measure has been satisfied for at least one previous
 packet; and means for terminating the iterative decoding process for the
 packet if: (1) the number of decoding iterations equals the predefined
 maximum number of iterations, or (2) the packet storage means is filled to
 within the predefined percentage of the storage capacity of the packet
 storage means, or (3) the number of decoding iterations equals the
 predefined minimum number of iterations, and if the error-detection
 measure has been satisfied for the at least one previous packet.
 In accordance with another aspect of the present invention, there is
 advantageously further provided an iterative decoder, comprising first and
 second decoders; an interleaver coupled to the first and second decoders
 and configured to interleave bits within a packet that was decoded by the
 second decoder and to provide the interleaved packet to the first decoder;
 a de-interleaver coupled to the first and second decoders and configured
 to de-interleave bits within a packet that was decoded by the first
 decoder and to provide the de-interleaved packet to the second decoder; an
 error-detection module coupled to the second decoder; an input packet
 buffer coupled to the first decoder; and a control unit coupled to the
 first and second decoders, the interleaver, the de-interleaver, the
 error-detection module, and the input packet buffer, the control unit
 being configured to terminate an iterative decoding process being
 performed on a packet if: (1) a number of decoding iterations equals a
 predefined maximum number of iterations, or (2) the error-detection module
 generates a satisfactory error-detection measure for two previous packets,
 or (3) the input packet buffer is filled to within a predefined percentage
 of the storage capacity of the input packet buffer.
 In accordance with another aspect of the present invention, there is
 advantageously further provided: A method of terminating an iterative
 decoding process being performed on a packet in an iterative decoder,
 comprising the steps of determining whether a number of decoding
 iterations equals a predefined maximum number of iterations; determining
 whether a packet storage element coupled to an input of the iterative
 decoder is filled to within a predefined percentage of the storage
 capacity of the packet storage element; determining whether the number of
 decoding iterations is greater than or equal to a predefined minimum
 number of iterations; determining whether an error-detection measure has
 been satisfied for at least one previous packet; and terminating the
 iterative decoding process for the packet if: (1) the number of decoding
 iterations equals the predefined maximum number of iterations, or (2) the
 number of decoding iterations is greater than or equal to the predefined
 minimum number of iterations, and the packet storage element is filled to
 within the predefined percentage of the storage capacity of the packet
 storage element, or: (3) the number of decoding iterations is greater than
 or equal to the predefined minimum number of iterations, and the
 error-detection measure has been satisfied for the at least one previous
 packet.
 In accordance with another aspect of the present invention, there is
 advantageously further provided an iterative decoder, comprising first and
 second decoding means for performing an iterative decoding process on a
 packet; packet storage means coupled to the first and second decoding
 means; means for determining whether a number of decoding iterations
 equals a predefined maximum number of iterations; means for determining
 whether the packet storage means is filled to within a predefined
 percentage of the storage capacity of the packet storage means; means for
 determining whether the number of decoding iterations is greater than or
 equal to a predefined minimum number of iterations; means for determining
 whether an error-detection measure has been satisfied for at least one
 previous packet; and means for terminating the iterative decoding process
 for the packet if: (1) the number of decoding iterations equals the
 predefined maximum number of iterations, or (2) the number of decoding
 iterations is greater than or equal to the predefined minimum number of
 iterations, and the packet storage means is filled to within the
 predefined percentage of the storage capacity of the packet storage means,
 or (3) the number of decoding iterations is greater than or equal to the
 predefined minimum number of iterations, and the error-detection measure
 has been satisfied for the at least one previous packet.
 The present invention will be more fully understood from the following
 detailed description of the preferred embodiments thereof, taken together
 with the drawings, in which:

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS
 FIG. 1 is a block diagram of a decoding processor 50, in accordance with an
 embodiment of the present invention. Processor 50 is preferably part of a
 digital receiver which receives analog signals. The received signals are
 digitized and preferably transformed to a scale in the range {-32,31}
 representing probability values in a logarithmic scale, as is known in the
 art. Alternatively, the scale may be in any other range and/or may be a
 non-logarithmic scale. Preferably, decoding processor 50 receives the
 digitized signals from a demodulator or channel de-interleaver (not
 shown), as is known in the art. The received digital signals were encoded
 before sending in accordance with a multi-code scheme, preferably
 including in series an outer coding scheme, interleaving, and an inner
 coding scheme. Alternatively or additionally, the multi-code scheme
 includes a Turbo code scheme, or any other suitable iterative scheme.
 The digitized data incoming to processor 50 is accumulated in two parallel
 buffers 62 and 64, wherein buffer 62 receives a first packet of data and
 buffer 64 receives a second packet. An inner decoder 68, which decodes the
 inner code, is connected alternately to buffers 62 and 64 via a switch 66.
 Decoder 68 is preferably an A Posteriori Probability (APP) decoder, also
 termed a Maximum A Posteriori (MAP) decoder. Such decoders are known in
 the art and are described, for example, in "Implementation and Performance
 of a Turbo/Map Decoder," by Steven S. Pietrobon, International Journal of
 Satellite Communications, vol. 16, 1998, pp.23-46, which is incorporated
 herein by reference, as well as in a U.S. patent application having Ser.
 No. 09/186,753, filed Nov. 5, 1998 and entitled "Efficient Trellis State
 Metric Normalization," which is assigned to the assignee of the present
 invention and is incorporated herein by reference. Further alternatively,
 decoder 68 may comprise other decoders known in the art including SOVA
 decoders.
 Two dual-port memories, preferably RAMs 52 and 54, are connected
 alternately to inner decoder 68 through two switches 56 and 58.
 Preferably, switch 56 conveys decoded output from decoder 68 to one of
 RAMs 52 and 54, while switch 58 conveys input to decoder 68 from the same
 one of the RAMs. Preferably, the output from decoder 68 is de-interleaved
 by a de-interleaver 72 upon its entrance to RAM 52 or 54 or upon its exit
 therefrom. Likewise, the input to decoder 68 through switch 58 is
 preferably interleaved by interleavers 74 associated with RAMs 52 and 54.
 An outer APP (or MAP) decoder 70, preferably similar to decoder 68 in
 structure although directed to decoding a different code, i.e., the outer
 code, is connected alternately to RAMs 52 and 54 via a switch 76.
 Preferably, decoder 70 comprises two output lines: a first output line 90
 which provides probability information on coded signals for further
 processing, and a second output line 92 which provides probability
 information on decoded data signals. A switch 78 connected to output line
 90 preferably alternately directs output from decoder 70 to interleavers
 74 of RAMs 52 and 54. After a sufficient number of iterations in processor
 50, the output from decoder 70 on output line 92 is preferably passed to a
 decision unit 80, which converts soft data to hard data. Preferably, the
 hard data is passed to a CRC checking unit 83 which determines and checks
 the CRC of the decoded packet.
 Preferably, decoder 68 outputs the decoded data as extrinsic information,
 i.e., as the difference between the LLR probabilities of its input data
 from switch 58 and its calculated improved LLR probabilities, as is known
 in the art and defined, for example, in the above mentioned publication by
 Hagenauer et al. Decoder 70, on the other hand, preferably has two output
 lines 90 and 92, as described above, one of which (preferably line 92)
 conveys extrinsic information as feedback to decoder 68 and the other of
 which (preferably line 90) conveys a priori probability information, i.e.,
 the calculated LLR probabilities, to decision unit 80.
 The decoded hard data is preferably output from decoding unit 50 via a
 switch 86 which directs the output on two separate lines 82 and 84,
 depending on in which of buffers 62 and 64 the original packet was stored.
 Preferably, a control unit 88 controls the operation of decoders 68 and
 70, the states of the switches, and other operations of processor 50.
 During operation, two successive packets of data are input to buffers 62
 and 64, respectively. Switches 66 and 56 are set to their upper states (as
 shown in FIG. 1), and decoder 68 performs a first cycle in which a first
 inner decoding iteration on the packet in buffer 62. In the first inner
 decoding iteration, decoder 68 receives the input packet from buffer 62
 and generates an output packet in RAM 52. The output packet is preferably
 de-interleaved in RAM 52 by de-interleaver 72, thus preparing the packet
 for input to decoder 70. The state of switch 58 does not affect the
 operation of decoder 68 and therefore does not matter or is disconnected.
 Thereafter, switches 56 and 66 are brought to their lower state, and
 switches 76 and 78 are brought to their upper states. At this point
 control unit 88 initiates operation of both decoders 68 and 70. Decoder 68
 performs a first inner decoding iteration on the packet in buffer 64 and
 generates an output packet in RAM 54. The output packet is preferably
 de-interleaved by de-interleaver 72 on its way into RAM 54 in preparation
 for input to decoder 70 during the next cycle of the processor.
 Alternatively or additionally, de-interleaver 72 de-interleaves the packet
 on its way out of RAM 54. Concurrently, decoder 70 performs a first outer
 decoding iteration on the packet in RAM 52. Decoder 72 operates on the
 de-interleaved packet in RAM 52 and generates an output packet back in RAM
 52. The output packet is interleaved, by interleaver 74 associated with
 RAM 52, in preparation for re-use by decoder 68.
 In a third operation cycle, switches 56, 58 and 66 are brought to their
 upper state and switches 76 and 78 are brought to their lower state, as in
 the first cycle. Decoder 68 receives input from both buffer 62 and RAM 52
 and performs a second inner decoding iteration on the packet in buffer 62.
 The output packet is passed to RAM 52 as in the first inner decoding
 iteration. Concurrently, decoder 70 performs a first outer decoding
 iteration on the packet from buffer 64. The output is returned to RAM 54
 to be interleaved by unit 74 in preparation for use by decoder 68.
 Thereafter the states of switches 56, 58, 66, 76 and 78 are changed,
 decoder 68 operates on the packet in buffer 64 and decoder 70 operates on
 the packet from buffer 62. Thus, decoders 68 and 70 interchangeably
 perform decoding iterations on the packets in buffer 62 and 64. Both of
 decoders 68 and 70 operate concurrently; and thus, using the same amount
 of hardware as processors known in the art, it is possible to achieve
 twice the decoding speed.
 Control unit 88 decides when to terminate the decoding of the packets,
 preferably in accordance with a method described hereinbelow. The output
 from decoder 70 is passed both through switch 78 and to decision unit 80,
 which derives hard data (0's and 1's) from the signs of the soft data in
 the packet, as described hereinabove or as is generally known in the art.
 The hard data is passed to CRC checking unit 83 which determines the CRC
 and passes it to control unit 88. According to the CRC and other
 information, control unit 88 decides whether to perform another decoding
 iteration as described further hereinbelow.
 Alternatively or additionally, after a predetermined number of decoding
 iterations, the decoding of each packet is terminated. Switch 86 is set on
 whichever of the two lines 82 or 84 the packet is to be output, and
 preferably switch 78 is disconnected. The output from decoder 70 is passed
 to decision unit 80, and from there is output via lines 82 or 84. At
 substantially the same time, a new packet of data is input to buffer 62 or
 64 in which the now-decoded packet was originally stored, and the decoding
 process is continued. Preferably, new packets are sequentially loaded into
 each of buffers 62 and 64 and then processed by decoder 68 independently
 of one other. Alternatively, buffers 62 and 64 are filled with new packets
 one after the other in immediate succession, so that two new packets enter
 the decoding process in immediately successive cycles.
 FIG. 2 is a flow chart illustrating an iterative decoding method performed
 by decoder 70 under supervision of control unit 88, in accordance with one
 embodiment of the present invention. Preferably, for each new packet
 entering processor 50, a counter of the number of decoding iterations
 performed is set to zero. For each outer decoding iteration of the packet,
 the counter is incremented. Until the counter reaches a predetermined
 minimum number of iterations (TR), the packet is automatically passed back
 from decoder 70 to decoder 68 for another decoding iteration. Preferably,
 the predetermined number (TR) is set to the minimal number of iterations
 which may achieve a sufficient decoding quality suitable for output.
 Further preferably, the predetermined number (TR) is between four and
 eight.
 After the predetermined number of initial iterations have been performed,
 decoder 70 and/or control unit 88 determines the minimal absolute value of
 the LLR probability values L of the bits in the packet,
 min(.vertline.L.vertline.), i.e., the LLR probability value among all of
 the bits in the packet that is closest to zero. (As noted hereinabove, the
 bit probabilities are measured in the log domain on a scale of -32 to 31,
 with the extrema of the scale corresponding to high probabilities of a one
 or a zero, respectively.) The minimal LLR probability represents a level
 of confidence that the LLR probability represents the correct hard bit
 value. Therefore, if the minimal LLR probability value is not above a
 predetermined absolute probability threshold, the decoding process
 continues. However, if the minimal LLR probability value is above the
 predetermined threshold, the CRC of the packet is preferably verified, and
 the decoding of the packet is terminated if the CRC is correct.
 Preferably, the minimal absolute value is calculated from the decoded data
 LLR probabilities on output line 90. Alternatively or additionally, the
 minimal absolute value is calculated from the coded data LLR a priori
 probabilities which corresponds to the extrinsic information on line 92,
 as described hereinabove and as is known in the art.
 Alternatively, decoder 70 checks either the minimum probability value or
 the CRC code, but not both. Further alternatively, any other measure of
 the progress of convergence of the probability values to the extrema is
 used instead of the minimum value. For example, the average or the median
 of the probability values of the bits may be compared to a different
 respective threshold. It is noted, however, that using the minimum is
 simple and generally requires less time to compute. In one embodiment of
 the present invention, instead of first calculating the minimum and only
 then comparing to the threshold, the probabilities are compared in
 sequence to the minimum threshold. If a bit with a probability lower than
 the threshold is found, the checking is terminated and another iteration
 is performed.
 Further, alternatively or additionally, the minimum probability is adjusted
 to ignore outliers. Preferably, a predetermined number of probability
 values beneath the minimum value are ignored.
 Further alternatively or additionally, the minimum or average probability
 is calculated on a subset of the bits in the packet, preferably on a
 random subset.
 It is noted that the method described hereinabove of determining when to
 terminate the iterative decoding, is not limited to use only with decoding
 processor 50. The above method may be used in any iterative decoder,
 including Turbo code decoders and Turbo-style decoders.
 It is further noted that although the above description refers to decoding
 methods using LLR probabilities in the log domain, the methods of the
 present invention may be used with other probability representations.
 Particularly, the methods of the present invention may be used with
 decoders, such as DSP floating-point-arithmetic decoders, which represent
 probabilities in the normal range, i.e., between 0 and 1. In such
 decoders, the method of choosing the minimum probability is adjusted so
 that the minimum is chosen relative to a hard data decision (`0` or `1`)
 represented by the probabilities.
 In another embodiment of the present invention, an iterative decoding
 system 100 includes a frame buffer 102, an inner decoder 104, an
 interleaver 106, a de-interleaver 108, an outer decoder 110, a decision
 unit 112, a CRC checking unit 114, and a control unit 116, as shown in
 FIG. 3. The interleaver 106 and the de-interleaver 108 may advantageously
 be implemented with RAM memory. The system 100 is advantageously part of a
 digital receiver that receives analog signals. The received signals are
 digitized and advantageously transformed to a scale in the range {-32,31}
 representing probability values in a logarithmic scale, as is known in the
 art. Alternatively, the scale may be in any other range and/or may be a
 non-logarithmic scale.
 Advantageously, the iterative decoding system 100 receives the digitized
 signals from a demodulator or channel de-interleaver (not shown), as is
 known in the art. The received digital signals were encoded before being
 transmitted in accordance with a multi-code scheme, advantageously
 including in series an outer coding scheme, interleaving, and an inner
 coding scheme. Alternatively or additionally, the multi-code scheme
 includes a Turbo code scheme, or any other suitable iterative scheme.
 The digitized data incoming to the system 100 is accumulated in the frame
 buffer 102, which receives the data in packets. The frame buffer 102 may
 advantageously be implemented with FIFO. The frame buffer 102 is
 configured to send a hardware control signal, denoted FAST_DECODE and
 described hereinbelow, to the control unit 116. The inner decoder 104,
 which decodes the inner code, is coupled to the frame buffer 102. The
 decoder 104 is advantageously an APP decoder (or MAP decoder), as known in
 the art. Further alternatively, the inner decoder 104 may comprise other
 decoders known in the art including, e.g., SOVA decoders.
 The inner decoder 104 is coupled to the de-interleaver 108. A decoded data
 signal is output from the inner decoder 104 and is de-interleaved by the
 de-interleaver 108. The de-interleaver 108 is coupled to the outer decoder
 110.
 The outer APP (or MAP) decoder 110, which is advantageously similar to the
 inner decoder 104 in structure although directed to decoding a different
 code (i.e., the outer code), is also coupled to the interleaver 106. The
 interleaver 106 is advantageously a pseudo-random interleaver, but may in
 the alternative be a block interleaver or a convolutional interleaver.
 Advantageously, the outer decoder 110 includes two output lines: a first
 output line that is connected to the interleaver 106, providing
 probability information on coded signals for further processing, and a
 second output line that is connected to the decision unit 112, providing
 probability information on decoded data signals. After a sufficient number
 of iterations in the decoding system 100, the output from the outer
 decoder 110 on the second output line is advantageously passed to the
 decision unit 112, which converts soft data to hard data. Advantageously,
 the hard data is passed to the CRC checking unit 114, which determines and
 checks the CRC of the decoded packet.
 Advantageously, the inner decoder 104 outputs the decoded data as extrinsic
 information, i.e., as the difference between the LLR probabilities of its
 input data and its calculated improved LLR probabilities, as is known in
 the art and defined, for example, in the above-mentioned publication by
 Hagenauer et al. The outer decoder 110, on the other hand, advantageously
 includes two output lines, as described above, one of which conveys
 extrinsic information as feedback to the inner decoder 104, and the other
 of which conveys a priori probability information, i.e., the calculated
 LLR probabilities, to the decision unit 112.
 The decoded hard data is advantageously output from the decoding system 100
 under the control of the control unit 116. The control unit 116 also
 controls other operations of the iterative decoding system 100. The
 control unit 100 may advantageously be a microprocessor. In the
 alternative, the control unit 116 may be implemented with any conventional
 processor, controller, microcontroller, or state machine.
 When both decoders 104, 110 have decoded a packet, the decoding system 100
 has performed one iteration. The control unit 116 decides when to
 terminate the decoding of the packets, advantageously in accordance with
 method steps described hereinbelow. The output from the outer decoder 110
 is passed to the decision unit 112, which derives hard data (0's and 1's)
 from the signs of the soft data in the packet, as described hereinabove or
 as is generally known in the art. The hard data is passed to the CRC
 checking unit 114, which determines the CRC in accordance with known
 methods and passes the CRC to the control unit 116. Based upon the CRC and
 other information, the control unit 116 decides whether to perform another
 decoding iteration as described further hereinbelow.
 Alternatively or additionally, after a predetermined number of decoding
 iterations, the decoding of each packet is terminated. The output from the
 inner decoder 110 is passed to the decision unit 112, and from there is
 output from the decoding system 100. At substantially the same time, a new
 packet of data is input to the frame buffer 102 (in which the now-decoded
 packet was originally stored), and the decoding process is continued.
 In accordance with one embodiment, the iterative decoding system 100, under
 the supervision of the control unit 116, performs the algorithm steps
 illustrated in the flow chart of FIG. 4 to stop the process of iteratively
 decoding a data packet. In step 200 a counter (not shown) of the number of
 decoding iterations performed is set to zero for each new packet that
 enters the system. The current iteration number is denoted ITER_NUM. The
 system then proceeds to step 202 and begins a decoding iteration. The
 system then proceeds to step 204 and increments the current iteration
 number, ITER_NUM. For each outer decoding iteration of the packet, the
 counter is incremented. Until the counter reaches a predefined minimum
 number of iterations, MIN_ITER_NUM, the packet is automatically passed
 back from the outer decoder to the inner decoder for another decoding
 iteration. Advantageously, the predefined minimum number of iterations,
 MIN_ITER_NUM, is set to the minimal number of iterations that may achieve
 a sufficient decoding quality suitable for output. Further advantageously,
 the predefined minimum number of iterations, MIN_ITER_NUM, is between four
 and eight. In one embodiment the predefined minimum number of iterations,
 MIN_ITER_NUM, is a four-bit frame parameter. After incrementing the
 current iteration number, ITER_NUM, the system proceeds to step 206.
 In step 206 the system determines whether the current iteration number,
 ITER_NUM, is equal to a predefined maximum number of iterations,
 MAX_ITER_NUM. Advantageously, the predefined maximum number of iterations,
 MAX_ITER_NUM, is between twelve and sixteen. In one embodiment the
 predefined maximum number of iterations, MAX_ITER_NUM, is a four-bit frame
 parameter. If the current iteration number, ITER_NUM, is equal to the
 predefined maximum number of iterations, MAX_ITER_NUM, the system proceeds
 to step 208. In step 208 the system stops performing decoding iterations
 on the data packet. If, on the other hand, the current iteration number,
 ITER_NUM, is not equal to the predefined maximum number of iterations,
 MAX_ITER_NUM, the system proceeds to step 210.
 In step 210 the system determines whether the current iteration number,
 ITER_NUM, is greater than or equal to the predefined minimum number of
 iterations, MIN_ITER_NUM. If the current iteration number, ITER_NUM, is
 greater than or equal to the predefined minimum number of iterations,
 MIN_ITER_NUM, the system proceeds to step 212. If, on the other hand, the
 current iteration number, ITER_NUM, is not greater than or equal to the
 predefined minimum number of iterations, MIN_ITER_NUM, the system returns
 to step 202 to perform another decoding iteration.
 In step 212 the system determines whether a condition flag denoted
 CRC_CHECK_MODE_OK is equal to one (i.e., whether the flag is set). The
 condition flag CRC_CHECK_MODE_OK flag, which is advantageously a flag in a
 decoding mode register (not shown) in the control unit, is advantageously
 written by the control unit. In one embodiment the CRC_CHECK_MODE_OK flag
 having a value of one indicates that the previous two iterations resulted
 in good cyclic redundancy checks (CRC). CRC is an error-detection method
 that is well known in the relevant art. In another embodiment the
 CRC_CHECK_MODE_OK flag having a value of one indicates that the CRC bits
 for the previous two iterations were identical. In another embodiment the
 CRC_CHECK_MODE_OK flag having a value of one indicates that the CRC bits
 for the previous two iterations were identical and that the previous two
 iterations resulted in good CRC. In another embodiment the
 CRC_CHECK_MODE_OK flag having a value of one indicates that the CRC bits
 for the previous iteration were good and that the entire packet is
 identical to the decoded packet on the previous iteration. In another
 embodiment a CONVERGE_DETECTED flag may be used in place of the
 CRC_CHECK_MODE_OK flag. The CONVERGE_DETECTED flag having a value of one
 indicates that the entire packet is identical to the decoded packet on the
 previous iteration. This is beneficial, for example, when the decoder has
 converged to an erroneous solution, and there is no need to continue
 trying to decode (i.e., there is no CRC in this mode). In other
 embodiments the CRC_CHECK_MODE_OK flag may having a value of one may
 indicate whether other known error-detection measures were satisfied for
 the previous two data packets.
 If in step 212 the CRC_CHECK_MODE_OK flag is equal to one, the system
 proceeds to step 208, terminating the iteration process for the data
 packet. If, on the other hand, the CRC_CHECK_MODE_OK flag is not equal to
 one (i.e., the flag is equal to zero, or cleared), the system proceeds to
 step 214.
 In step 214 the system determines whether a hardware control signal denoted
 FAST_DECODE is equal to one. The FAST_DECODE hardware control signal may
 advantageously be used in a multi-user decoding system, in which a signal
 is sent by the demodulator (not shown) to speed up the decoding system.
 The FAST_DECODE hardware control signal may advantageously be generated by
 an external FIFO to tell the decoding system to finish decoding a packet
 as soon as possible after the minimum number of iterations, MIN_ITER_NUM,
 has been performed. Alternatively, the FAST_DECODE hardware control signal
 may be driven by the FIFO of the input frame buffer to the decoding
 system. A threshold is set on the FIFO such that if the FIFO is filled
 with packets to a level that is below the threshold, the decoding system
 can run the maximum number iterations, MAX_ITER_NUM. If the FIFO is close
 to full (i.e., if the threshold is met or exceeded), the decoding system
 will run only the minimum number of iterations, MIN_ITER_NUM. Thus, if the
 FIFO is filled to within a predefined percentage of the storage capacity
 of the FIFO, the FAST_DECODE hardware control signal is driven. The
 threshold level may thus advantageously be set on the FIFO to drive the
 FAST_DECODE hardware control signal in the event the decoding system
 realizes that it cannot serve all of the packets waiting in the input
 frame buffer.
 If in step 214 the FAST_DECODE hardware control signal is equal to one, the
 system proceeds to step 208, stopping the iteration process for the data
 packet. If, on the other hand, the FAST_DECODE hardware control signal is
 not equal to one (i.e., it is equal to zero), the system returns to step
 202 to perform another decoding iteration.
 It would be understood by those skilled in the art that the method steps of
 FIG. 4 may be performed by any iterative decoder including, e.g., Turbo
 decoders or Turbo-style decoders. It is well known that the Turbo decoding
 principal can be used for iterating between an equalizer and a decoder, or
 between a demodulator and a decoder. Therefore, it would also be
 understood by those skilled in the art that the method steps of FIG. 4 may
 be performed in Turbo equalization (including a decoder).
 In accordance with another embodiment, the iterative decoding system 100 of
 FIG. 3, under the supervision of the control unit 116, performs the
 algorithm steps illustrated in the flow chart of FIG. 5 to stop the
 process of iteratively decoding a data packet. In step 300 a counter (not
 shown) of the number of decoding iterations performed is set to zero for
 each new packet that enters the system. The current iteration number is
 denoted ITER_NUM. The system then proceeds to step 302 and begins a
 decoding iteration. The system then proceeds to step 304 and increments
 the current iteration number, ITER_NUM. For each outer decoding iteration
 of the packet, the counter is incremented. Until the counter reaches a
 predefined minimum number of iterations, MIN_ITER_NUM, the packet is
 automatically passed back from the outer decoder to the inner decoder for
 another decoding iteration. Advantageously, the predefined minimum number
 of iterations, MIN_ITER_NUM, is set to the minimal number of iterations
 that may achieve a sufficient decoding quality suitable for output.
 Further advantageously, the predefined minimum number of iterations,
 MIN_ITER_NUM, is between four and eight. In one embodiment the predefined
 minimum number of iterations, MIN_ITER_NUM, is a four-bit frame parameter.
 After incrementing the current iteration number, ITER_NUM, the system
 proceeds to step 306.
 In step 306 the system determines whether the current iteration number,
 ITER_NUM, is equal to a predefined maximum number of iterations,
 MAX_ITER_NUM. Advantageously, the predefined maximum number of iterations,
 MAX_ITER_NUM, is between twelve and sixteen. In one embodiment the
 predefined maximum number of iterations, MAX_ITER_NUM, is a four-bit frame
 parameter. If the current iteration number, ITER_NUM, is equal to the
 predefined maximum number of iterations, MAX_ITER_NUM, the system proceeds
 to step 308. In step 308 the system stops performing decoding iterations
 on the data packet. If, on the other hand, the current iteration number,
 ITER_NUM, is not equal to the predefined maximum number of iterations,
 MAX_ITER_NUM, the system proceeds to step 310.
 In step 310 the system determines whether a condition flag denoted
 CRC_CHECK_MODE_OK is equal to one (i.e., whether the flag is set). The
 condition flag CRC_CHECK_MODE_OK flag, which is advantageously a flag in a
 decoding mode register (not shown) in the control unit, is advantageously
 written by the control unit. In one embodiment the CRC_CHECK_MODE_OK flag
 having a value of one indicates that the previous two iterations resulted
 in good CRC. In another embodiment the CRC_CHECK_MODE_OK flag having a
 value of one indicates that the CRC bits for the previous two iterations
 were identical. In another embodiment the CRC_CHECK_MODE_OK flag having a
 value of one indicates that the CRC bits for the previous two iterations
 were identical and that the previous two iterations resulted in good CRC.
 In another embodiment the CRC_CHECK_MODE_OK flag having a value of one
 indicates that the CRC bits for the previous iteration were good and that
 the entire packet is identical to the decoded packet on the previous
 iteration. In another embodiment a CONVERGE_DETECTED flag may be used in
 place of the CRC_CHECK_MODE_OK flag. The CONVERGE_DETECTED flag having a
 value of one indicates that the entire packet is identical to the decoded
 packet on the previous iteration. This is beneficial, for example, when
 the decoder has converged to an erroneous solution, and there is no need
 to continue trying to decode (i.e., there is no CRC in this mode). In
 other embodiments the CRC_CHECK_MODE_OK flag, having a value of one, may
 indicate whether other known error-detection measures were satisfied for
 the previous two data packets.
 If in step 310 the CRC_CHECK_MODE_OK flag is equal to one, the system
 proceeds to step 308, terminating the iteration process for the data
 packet. If, on the other hand, the CRC_CHECK_MODE_OK flag is not equal to
 one (i.e., the flag is equal to zero, or cleared), the system proceeds to
 step 312.
 In step 312 the system determines whether the current iteration number,
 ITER_NUM, is equal to the predefined minimum number of iterations,
 MIN_ITER_NUM. If the current iteration number, ITER_NUM, is equal to the
 predefined minimum number of iterations, MIN_ITER_NUM, the system proceeds
 to step 314. If, on the other hand, the current iteration number,
 ITER_NUM, is not equal to the predefined minimum number of iterations,
 MIN_ITER_NUM, the system returns to step 302 to perform another decoding
 iteration.
 In step 314 the system determines whether a hardware control signal denoted
 FAST_DECODE is equal to one. The FAST_DECODE hardware control signal may
 advantageously be used in a multi-user decoding system, in which a signal
 is sent by the demodulator (not shown) to speed up the decoding system.
 The FAST_DECODE hardware control signal may advantageously be generated by
 an external FIFO to tell the decoding system to finish decoding a packet
 as soon as possible after the minimum number of iterations, MIN_ITER_NUM,
 has been performed. Alternatively, the FAST_DECODE hardware control signal
 may be driven by the FIFO of the input frame buffer to the decoding
 system. A threshold is set on the FIFO such that if the FIFO is filled
 with packets to a level that is below the threshold, the decoding system
 can run the maximum number iterations, MAX_ITER_NUM. If the FIFO is close
 to full (i.e., if the threshold is met or exceeded), the decoding system
 will run only the minimum number of iterations, MIN_ITER_NUM. Thus, if the
 FIFO is filled to within a predefined percentage of the storage capacity
 of the FIFO, the FAST_DECODE hardware control signal is driven. The
 threshold level may thus advantageously be set on the FIFO to drive the
 FAST_DECODE hardware control signal in the event the decoding system
 realizes that it cannot serve all of the packets waiting in the input
 frame buffer.
 If in step 314 the FAST_DECODE hardware control signal is equal to one, the
 system proceeds to step 308, stopping the iteration process for the data
 packet. If, on the other hand, the FAST_DECODE hardware control signal is
 not equal to one (i.e., it is equal to zero), the system returns to step
 302 to perform another decoding iteration.
 It would be understood by those skilled in the art that the method steps of
 FIG. 5 may be performed by any iterative decoder including, e.g., Turbo
 decoders or Turbo-style decoders. It is well known that the Turbo decoding
 principal can be used for iterating between an equalizer and a decoder, or
 between a demodulator and a decoder. Therefore, it would also be
 understood by those skilled in the art that the method steps of FIG. 5 may
 be performed in Turbo equalization (including a decoder).
 Thus, a novel, efficient, iterative decoder has been described. Those of
 skill in the art would understand that the various illustrative logical
 blocks and algorithm steps described in connection with the embodiments
 disclosed herein may be implemented or performed with a digital signal
 processor (DSP), an application specific integrated circuit (ASIC),
 discrete gate or transistor logic, discrete hardware components such as,
 e.g., registers and FIFO, a processor executing a set of firmware
 instructions, or any conventional programmable software module and a
 processor. The processor may advantageously be a microprocessor, but in
 the alternative, the processor may be any conventional processor,
 controller, microcontroller, or state machine. The software module could
 reside in RAM memory, flash memory, registers, or any other form of
 writable storage medium known in the art. Those of skill would further
 appreciate that the data, instructions, commands, information, signals,
 bits, symbols, and chips that may be referenced throughout the above
 description are advantageously represented by voltages, currents,
 electromagnetic waves, magnetic fields or particles, optical fields or
 particles, or any combination thereof.
 It will be appreciated that the preferred embodiments described above are
 cited by way of example, and the full scope of the invention is limited
 only by the claims.