Iterative decoder employing multiple external code error checks to lower the error floor

0001This application is a continuation of U.S. application Ser. No. 10/892,738, filed Jul. 16, 2004, now U.S. Pat. No. 7,310,768; which is a continuation of U.S. application Ser. No. 09/865,958, filed May 25, 2001, now U.S Pat. No. 6,810,502; which is a continuation-in-part of U.S. application Ser. No. 09/492,962 filed Jan. 28, 2000, now U.S. Pat. No. 6,606,724; the above-identified applications are incorporated herein by reference in their entirety.

TECHNICAL FIELD

0002The present invention relates generally to communication systems and iterative decoding performance. A method and apparatus for decoding the serial concatenation of multiple external code blocks with serially concatenated block- and convolutional-coded data is presented. An example of how these concepts may be applied to parallel concatenated codes is also presented.

BACKGROUND

0003Communication systems are often limited in terms of transmitter power and spectrum availability. For these and other reasons, it is often a goal of digital communications design to maximize the transmission bit rate R and minimize the probability of bit error, or Bit Error Rate (BER), for a given system power S, and bandwidth B. The minimum bandwidth (BW) required to transmit at rate (R) is known to be Rs/2, where Rs is the symbol rate. A limit on the transmission rate, called the system capacity, is based on the channel BW and the signal to noise ratio (SNR). This limit theorem, also called the Shannon Noisy Channel Coding Theorem, states that every channel has a channel capacity C which is given by the formula, C=BW log₂(1+SNR), and that for any rate R<C, there exist codes of rate R_Cwhich can have an arbitrarily small decoding BER.

0004For some time, the digital communications art has sought a coding/decoding algorithm which would reach the Shannon limit. Recently, coding/decoding schemes, called “Turbo Codes,” have been determined to achieve fairly reliable data communication at an SNR that is very close to the Shannon Limit for modulation constrained codes.

0005One form of turbo decoding operates upon serial concatenated codes. Not all of such serially concatenated codes are iteratively decoded in practice, however. As an example, a serial concatenation of an outer, block code—such as a Reed Solomon code—and an inner, convolutional code, can be found in many communications and data storage applications requiring very low bit error rates. This type of serial concatenation is used, for example, in DBS (Direct Broadcast Satellite) standards. However, in practice, this serial concatenated code is not iteratively decoded.

0006One such serial concatenated system <b>100</b> is illustrated in <figref idref="DRAWINGS">FIG. 1</figref>. The serial concatenated system <b>100</b> includes a transmitter portion <b>102</b> for communicating encoded information to a receiver portion <b>104</b> via a communication channel <b>106</b>. The transmitter portion <b>102</b> uses an outer code encoder or block encoder <b>108</b> (e.g., a Reed-Solomon encoder) to encode input bits. The output of the outer code encoder <b>108</b> is then provided to an interleaver <b>110</b> wherein the signal bit order is shuffled in a predetermined manner. Next, the output of the interleaver is provided to an inner code encoder (e.g., convolutional encoder) <b>112</b>. The output of the inner code encoder <b>112</b> is then sent to a bit-to-constellation mapper, modulated by modulator <b>114</b> and transmitted over the communication channel <b>106</b> to the receiver portion <b>104</b> for decoding and processing.

0007Once demodulated by demodulator <b>116</b>, the classical approach for decoding a serial concatenated system <b>100</b> is to apply a soft-decision inner code decoder (e.g., Viterbi decoder) <b>118</b> that receives as inputs soft symbols and outputs hard bit estimates for the inner block code. The outputs of the inner code decoder <b>118</b> are then byte-deinterleaved by deinterleaver <b>120</b> and provided to an outer code decoder <b>122</b> (generally a block decoder such as a Reed-Solomon decoder) that can correct multiple byte errors in a block. If the outer code decoder <b>122</b> indicates that the number of errors is beyond its correction capability, it may indicate so and no corrections are made.

0008In effect, this classical approach to concatenated decoding decomposes the task into two independent procedures: one for the inner code, and another for the outer code. An “optimal” decoder is then selected and applied for each of these procedures. However, although each decoder may be optimal for its specific task, the overall composite system may not be optimal for a given concatenated code. This is because (1) the Reed-Solomon decoder uses hard—rather than soft—decision data, and (2) the Viterbi decoder performance could be improved in a second pass decoding operation. In particular, error bursts, which are observed in the first-pass decoding, could be broken up by using the bit decisions from blocks which were successfully decoded by a Reed-Solomon decoder. This operation would, in turn, impact a second-pass Reed-Solomon decoding of the data, perhaps enabling the Reed-Solomon decoder to correct another block that previously was considered uncorrectable. In principle, the sharing of outer-to-inner code decoding information could be re-iterated, resulting in even further improvements. In fact, this technique is similar to turbo decoding in a parallel or serial concatenated code context, with bit-by-bit maximum a posteriori probability (MAP) decoding.

0009Various iterative (turbo-like) decoding approaches have been used in simulation to decode serial concatenations of convolutional and Reed-Solomon codes. One problem in such decoding processes is determining how the Viterbi algorithm is to be modified to accommodate inputs from Reed-Solomon decoded blocks that are correct. One attractive approach involves finding a method that efficiently forces a Viterbi decoder to constrain certain locations in a data record to desired output logic levels.

0010As previously indicated, the aforesaid serial concatenation of a Reed Solomon and a convolutional code can be iteratively decoded. However, better results are achievable if the component codes are specifically designed with the iterative decoding process in mind. ‘Turbo codes’ are examples of such codes.

0011A limitation of conventional turbo decoders is the inability to reach very low bit error rate (BER) floors; this inhibits their broad application to video transport, which requires very low BERs. One approach employed in the art to try to reduce the BER floor has been geared towards choosing good codes and topologies. These approaches try to make more efficient the already existent methods of trying to perform turbo decoding, but sometimes practical implementations that achieve the desired level of performance are difficult to find. For this reason, the serial concatenation of an additional, external decoder, such as a Reed-Solomon decoder, is sometimes used in an attempt to drive the BER floor lower. For some applications, whereby only the turbo code is used, one may not be able to achieve sufficiently low BER floors as desired or required within a given application.

0012Further limitations and disadvantages of conventional and traditional systems will become apparent to one of skill in the art through comparison of such systems with the present invention as set forth in the remainder of the present application with reference to the drawings.

SUMMARY OF THE INVENTION

0013Various aspects of the present invention can be found in a turbo decoder that employs iterative decoding, and additionally employs a turbo code-external ‘external decoder’ in the iterative decoding process. This external decoder may be a decoder for an error detection code, such as a block Cyclic Redundancy Check (CRC) code, or a block algebraic error correction code, such as a Reed Solomon or BCH code. Multiple external code “sub-blocks” (upon which the CRC or Reed Solomon decoder operate upon) exist within a single block being decoded by the turbo decoder.

0014Other aspects of the invention can be seen in a conventional serial concatenation of a convolutional code with a Reed Solomon or similar algebraic decoder. In fact, the role and utilization of the Reed Solomon, or ‘other similar algebraic coder’ is analogous to the external decoder within the turbo decoder application. The only difference is that the ‘external code’ is married with a turbo code in the turbo code application; whereas, the ‘external code’ is married with a convolutional code in the conventional serial concatenation case.

0015The invention involves the feedback of high-confidence ‘correct’ hard decisions from an external decoder to the turbo decoder (or convolutional decoder). More importantly, it outlines techniques by which information concerning these high confidence decisions may be imposed as constraints and thereby exploited within the turbo decoder (or convolutional decoder).

0016The feedback from the external decoder is employed within one or both of the inner and/or the outer decoder (SISO) of a serial turbo concatenated code—or the inner code of a conventional concatenated code. The method for employment for this feedback information within the SISOs may involve one or both of decision-forcing and/or input data overloading. Decision-forcing may be characterized as a method that renormalizes selective state metrics so that the decoder is prohibited from considering undesired decision outcomes. Input data overloading may be characterized as muxing input data with extreme values, so that this data can be overwritten in selected locations, and thereby influence the decoder to favor desired decision outcomes. Moreover, various aspects of the invention are applicable to areas beyond those of serially concatenated codes. One such extension includes their application using a parallel concatenated code.

0017Other systems, methods, features and advantages of the invention will be or will become apparent to one with skill in the art upon examination of the following figures and detailed description. It is intended that all such additional systems, methods, features and advantages be included within this description, be within the scope of the invention, and be protected by the accompanying claims.

BRIEF DESCRIPTION OF THE DRAWINGS

The components in the figures are not necessarily to scale, emphasis instead being placed upon illustrating the principles of the invention. In the figures, like reference numerals designate corresponding parts throughout the different views.

In addition, throughout the various drawings, those lines that are dashed include optional items. The operation of the various items, signals, and elements that are represented by such lines may be included in the embodiment shown, or they may be omitted without impeding the operation of aspects of the invention.

<figref idref="DRAWINGS">FIG. 1</figref> is a schematic diagram of a conventional Serial Concatenated Coding system.

<figref idref="DRAWINGS">FIG. 2</figref> is a schematic diagram of an exemplary communications system (involving iterative decoding of the serial concatenation of an inner convolutional code and outer Reed Solomon code) built in accordance with the invention.

<figref idref="DRAWINGS">FIG. 3</figref> provides exemplary details of a convolutional encoder for inner encoding data in the communication system of <figref idref="DRAWINGS">FIG. 2</figref>.

<figref idref="DRAWINGS">FIG. 4</figref> provides exemplary details of a modified encoder for encoding data status information for use by the communication system of <figref idref="DRAWINGS">FIG. 2</figref>.

<figref idref="DRAWINGS">FIG. 5</figref> is a schematic diagram of an alternate embodiment of a pipelined communications system according to the present invention.

<figref idref="DRAWINGS">FIG. 6</figref> is a diagram illustrating a turbo decoder bit error rate (BER) versus energy per source bit (E.sub.b/N.sub.0) characteristic.

<figref idref="DRAWINGS">FIG. 7A</figref> is a functional diagram illustrating an embodiment of a nonsystematic encoder.

<figref idref="DRAWINGS">FIG. 7B</figref> is a functional diagram illustrating an embodiment of a nonsystematic code trellis.

<figref idref="DRAWINGS">FIG. 8A</figref> is a functional diagram illustrating an embodiment of a recursive systematic encoder.

<figref idref="DRAWINGS">FIG. 8B</figref> is a functional diagram illustrating an embodiment of a recursive systematic code trellis.

<figref idref="DRAWINGS">FIG. 9</figref> is a system diagram illustrating an embodiment of a turbo codec built in accordance with the present invention.

<figref idref="DRAWINGS">FIG. 10A</figref> is a system diagram illustrating an embodiment of a soft in/soft out functional block operating built in accordance with the present invention.

<figref idref="DRAWINGS">FIG. 10B</figref> is a system diagram illustrating an embodiment of a soft in/soft out functional block that generates extrinsic information in accordance with the present invention.

<figref idref="DRAWINGS">FIG. 11A</figref> is a system diagram illustrating an embodiment of a serial concatenated code turbo decoder that feeds back external decoding information to an outer SISO.

<figref idref="DRAWINGS">FIG. 11B</figref> is a system diagram illustrating an embodiment of a serial concatenated code turbo decoder that feeds back external decoding information to an inner SISO using a MUX method of decision forcing in accordance with the present invention.

<figref idref="DRAWINGS">FIG. 12</figref> is a system diagram illustrating an embodiment of a turbo decoder, having a path restriction (decision-forcing) implementation, that is built in accordance with the present invention.

<figref idref="DRAWINGS">FIG. 13</figref> is a system diagram illustrating an embodiment of a parallel concatenation encoder built in accordance with the present invention.

<figref idref="DRAWINGS">FIG. 14</figref> is a system diagram illustrating an embodiment of a parallel concatenation decoder built in accordance with the present invention.

<figref idref="DRAWINGS">FIG. 15</figref> is a functional diagram illustrating a parallel concatenation code application operating in a decision forcing, or path restriction, implementation in accordance with the present invention.

<figref idref="DRAWINGS">FIG. 16</figref> is a functional diagram illustrating a parallel concatenation code application with feedback operating in an overloading implementation in accordance with the present invention.

<figref idref="DRAWINGS">FIG. 17</figref> is a functional flow chart illustrating an embodiment of a turbo decoder method performed in accordance with the present invention.

<figref idref="DRAWINGS">FIG. 18</figref> is a functional flow chart illustrating another embodiment of a turbo decoder method performed in accordance with the present invention.

DETAILED DESCRIPTION

0042One example of digital video processing is that employed using the motion picture expert group (MPEG) standard. In the MPEG standard, a block consists of 188 bytes of data. In one embodiment of the present invention, the turbo decoding system operates on nominally 10 MPEG blocks of source data in a turbo decoder frame. A cyclic redundancy check (CRC) check is contained within each of these MPEG blocks. One purpose of the CRC check is to ensure that the MPEG decoder has advance knowledge of whether the bits that it is receiving are correct or not. A turbo decoder operable in accordance with the present invention is able to take advantage of the redundancy of the CRC to further improve the decoding performance. During iterations before the final iteration, this improvement in decoding performance is achieved.

0043From one perspective, when a block covered by a CRC (henceforward, a “CRC block”) decodes correctly, it may be assumed with a relative high degree of certainty that this particular segment of the decoded data is known with a very high probability. The turbo decoder then may use this knowledge to assign a very high confidence level to that segment of data. The turbo decoder can then feed this data back to an inner decoder and also to an outer decoder in its next iteration. By doing this, the decoding performance of the next iterative pass is improved. Since the inner decoder uses interleaved or order-scrambled versions of the outer decoded bits, the increase in performance can be significant. The reason for this is that the high confidence bits are scattered throughout an inner decoded frame, and can thereby influence the decoding of the bits surrounding them, in subsequent decoding iterations.

0044While the MPEG encoded video data is one type of video data that may have CRC checks, any other type of data having such redundancy will also benefit from the present invention. The present invention is operable to augment the performance of any other turbo decoder solution borrowing on the additional redundancy of bits intended for an error detection (or error correcting) function. This will enhance decoding performance and drive down a bit error rate (and lower the BER floor) beyond solutions that do not involve external codes (such as CRCs) within the iterative decoding process.

0045The present invention is geared and very effective to lower the BER floor—i.e., the region in the turbo decoder BER characteristic that flattens, or saturates. In the floor regions, the BER is already very low. Since there is already a high likelihood that the data are error free, some blocks of bits, covered by CRC block checks, for example, are likely to be ‘clean.’ Fortunately, it is precisely in these low BER regions where a reduction in BER floor is needed, and the present invention will perform best. It requires that some of these blocks are, indeed, ‘error free.’

0046<figref idref="DRAWINGS">FIG. 2</figref> is a schematic diagram of an exemplary communications system (involving iterative decoding of the serial concatenation of an inner convolutional code and outer Reed Solomon code) built in accordance with the invention. The communications system includes a receiver <b>200</b> comprising at least one pipeline decoder unit <b>201</b>. As will be appreciated, the pipeline decoder unit <b>201</b> includes decoding functionality that efficiently utilizes inputs from previously decoded blocks to improve receiver performance and coding gain.

0047One obstacle to direct VLSI implementations of iterative concatenated decoding is the required processing speed. For example, if serial data is input at 20 Msymbols/sec, and four iterations are desired, the Viterbi and Reed-Solomon decoders must operate at four times the symbol rate (80 Msymbols/sec)—if the streaming data is to be processed in real time. With the disclosed pipeline approach, however, the processing speed of elements in the pipelined datapaths does not need to be increased with respect to those found in a classical concatenated decoder.

0048Referring more particularly to <figref idref="DRAWINGS">FIG. 2</figref>, received data is first demodulated by a demodulator <b>202</b> to produce quantized data symbols, called ‘soft-decision symbols,’ delivered at the channel symbol rate. This soft decision symbol data may then be provided to an erasure insertion circuit <b>204</b>, in which an erasure is inserted, before the first decoding pass, at the point where the symbol was punctured by the transmitter. Puncturing coded encoder outputs is acceptable for transmission purposes because of the redundancy of information that is created within typical encoders. As discussed in greater detail below, the pipeline decoder units <b>201</b> may be advantageously isolated from puncture-specific procedures.

0049The soft-decision symbols provided by the erasure insertion circuitry <b>204</b> are first decoded by an inner or first decoder <b>206</b> (e.g., a Viterbi or other convolutional decoder, or a TCM decoder), to produce first decoded data. The first decoded data is then deinterleaved by a deinterleaver <b>208</b> prior to provision to an outer or second decoder <b>210</b> (e.g., an algebraic and/or block decoder such as a Reed-Solomon decoder).

0050The Reed-Solomon decoder <b>210</b> has two outputs, which are provided to the first pipeline decoder unit <b>201</b>: the actual bits of a decoded Reed-Solomon block, and a decode status signal output that indicates whether an associated Reed-Solomon block was decoded without error. The Reed-Solomon decoding status signal is replicated for each Reed-Solomon bit, forming a stream of status bits. In the disclosed embodiment, the Reed-Solomon data bits are provided to a data interleaver <b>212</b> of the first pipeline decoder unit <b>201</b>, while the decode status bits are interleaved by a control interleaver <b>214</b>. The data interleaver <b>212</b> and control interleaver <b>214</b> function to spread the status and data bits over multiple Reed-Solomon blocks of data. The data interleaver <b>212</b> preferably functions in a manner similar to the interleaver used by the transmitter to generate the serial concatenated data received by the receiver <b>200</b>.

0051After interleaving, the Reed-Solomon data bits are re-encoded by convolutional encoder <b>216</b> to form encoded outputs. Again, the convolutional encoder <b>216</b> preferably functions in a like manner to the inner decoder used by the transmitter to produce the serial concatenated code data. As discussed more fully below in conjunction with <figref idref="DRAWINGS">FIG. 4</figref>, a similar encoding process is performed on the interleaved status bits by a “modified encoder” <b>220</b>, such that a Viterbi or third decoder <b>226</b> can determine whether or not data bits produced by the convolutional encoder <b>216</b> evolved entirely from reliable Reed-Solomon-decoded blocks.

0052The Viterbi decoder <b>226</b> of the pipeline decoder unit <b>201</b> of the disclosed embodiment of the invention is configured to behave in a like manner to a MAP sequence decoder when provided with high-reliability data from successfully decoded Reed-Solomon blocks. In particular, the binary “hard-decision” data provided by the convolutional encoder <b>216</b> is provided to a soft-decision minimum-/maximum-scale level mapper <b>218</b>, which functions to produce highly reliable soft-decision data. For example, a logic level “0” may be mapped to a minimum-scale soft-decision value (e.g., 0000 with 4-bit unsigned binary quantization), and a logic level “1” mapped to the maximum-scale soft-decision value (e.g., 1111 with 4-bit unsigned binary quantization). Next, the “mapped” datastream (or Reed-Solomon-forced decision symbol data) is time-aligned with the soft-decision symbol data produced by the erasure insertion circuitry <b>204</b>. The temporal alignment is provided by delay circuitry <b>224</b>. The time-aligned datastreams are then provided to the parallel inputs of multiplexing circuitry <b>222</b>.

0053The multiplexing circuitry <b>222</b> receives the output of the modified encoder <b>220</b> as a control signal to selectively determine which of the datastreams to provide to the third decoder <b>226</b>. When Reed-Solomon forced-decision symbol data is available from a successfully decoded Reed-Solomon block, the multiplexing circuitry <b>222</b> passes that data to the third decoder <b>226</b>. When the incumbent “mapped” element is from a failed Reed-Solomon block, the multiplexing circuitry instead passes the delayed soft-decision symbol data from block <b>224</b> to the third decoder <b>226</b>. The third decoder <b>226</b> decodes the output of the multiplexing circuitry <b>222</b> to provide “pipelined” decoded data characterized by having a smaller bit error rate than the decoded data provided by the first decoder <b>206</b>. In particular, the third decoder <b>226</b> benefits from the entire concatenated coding gain of the first decoding pass.

0054The output of the third decoder <b>226</b> is next deinterleaved by deinterleaver <b>228</b>, whose output is provided to a fourth/Reed-Solomon decoder <b>230</b>. As with the Reed-Solomon decoder <b>210</b>, the Reed-Solomon decoder <b>230</b> of the pipeline decoder unit <b>201</b> may include both a decoded data datastream, as well as a decode status signal datastream. These datastreams, as well as the output of the delay circuitry <b>224</b>, may be provided to an additional pipeline decoder unit <b>201</b>.

0055It is contemplated that any number of additional pipeline decoder units <b>201</b> may be similarly utilized until the desired coding gains and BER is achieved. In another contemplated embodiment of the invention, the clock rate for the decoder <b>200</b> could be increased and additional multiplexing circuitry provided such that the first decoder <b>206</b> could be leveraged to perform the function of the third decoder <b>226</b>. Similarly, the second decoder <b>210</b> could be reused to perform the function of the fourth decoder <b>230</b>. By using an appropriate clocking scheme, additional “pipelined” iterations could be performed by the first decoder <b>206</b> and the second decoder <b>210</b>. In this manner, the hardware overhead associated with the disclosed received <b>200</b> may be reduced.

0056Although the illustrated receiver <b>200</b> makes use of a convolutional inner code and an algebraic or Reed-Solomon outer code, it is contemplated that a decoder according to the present invention may be adapted to utilize TCM codes and/or other types of block codes.

0057<figref idref="DRAWINGS">FIG. 3</figref> provides exemplary details of a convolutional encoder <b>216</b> for inner encoding data in the communication system of <figref idref="DRAWINGS">FIG. 2</figref>. The convolutional encoder <b>216</b> receives a continuous sequence of data input bits that are mapped into a continuous sequence of encoder data bit outputs. The convolutional encoder <b>216</b> comprises a finite state shift register formed of series-connected flip-flops <b>300</b> and <b>302</b>. In accordance with conventional encoder architectures, the data inputs bits, as well as the outputs of each of the flip-flops <b>300</b> and <b>302</b> are provided to a first exclusive OR (XOR) gate <b>304</b>. The XOR gate <b>304</b> produces a first data bit output. The data bit inputs are likewise provided to a second XOR gate <b>306</b>, which also receives the output of the flip-flop <b>302</b>. The second exclusive OR gate <b>306</b> produces a second data output bit. As will be appreciated, the first and second outputs of the convolutional encoder <b>216</b> relate to a rate ½ code, and these outputs may be converted from a parallel format to a serial format via a converter (not shown).

0058<figref idref="DRAWINGS">FIG. 4</figref> provides exemplary details of a modified encoder <b>220</b> for encoding decode status signals generated by an outer decoder <b>210</b>. The modified encoder <b>220</b> structurally resembles the convolutional encoder <b>216</b>, with the exception that the XOR gates <b>304</b> and <b>306</b> in the convolutional encoder <b>216</b> are replaced by AND gates <b>404</b> and <b>406</b>. The incoming decode status signal/control bits, as well as the outputs of flip-flops <b>400</b> and <b>402</b> are provided to the three input AND gate <b>404</b>, which produces a first control bit. The decode status signals and the output of the flip-flop <b>402</b> are provided to the two input AND gate <b>406</b>, which produces a second control bit. This arrangement is advantageous because when the output of the convolutional encoder <b>216</b> has no dependency on input data that is invalid, the modified encoder <b>220</b> signals that the output is valid. This is true even if the code in question may have shift register entries which are invalid but not accessed, as is the case for the control bit produced by AND gate <b>406</b>. As previously discussed, the outputs of the modified encoder <b>220</b> may be used to control the multiplexing circuitry <b>222</b>, which determines whether the re-encoded data is used.

0059As illustrated in the disclosed embodiment of the invention, the symbols erased by puncturing (at the transmitter) are inserted before the first decoding pass. Thus, decoding operations performed by the pipeline decoder unit(s) <b>201</b> need not perform puncture-specific procedures. Instead, the pipelined decoder unit(s) <b>201</b> can be configured to operate as fixed-rate devices (with the possible exception that the trace back length in the Viterbi decoder(s) <b>216</b> may be lengthened for optimal decoding performance when punctured data is present). It is also noted that in secondary decoding passes, the erased data that was re-inserted does not necessarily remain indeterminate (i.e., somewhere between a logic level “1” and “0”) as it was when initially inserted. If the re-inserted data arises from a bit that was correctly decoded in a Reed-Solomon block evaluation, then its value is known with very high probability. Thus, it is possible to correctly infer the value of untransmitted punctured bits and use this information in all subsequent decoding passes. This enhances the performance of the receiver <b>200</b> in high data rate applications involving puncturing.

0060In the disclosed embodiment of the invention, the Viterbi or third decoder <b>226</b> of the pipeline decoder unit <b>201</b> is described as utilizing forced decision data, which forces the third decoder <b>226</b> to behave much like a MAP sequence processor. Although not precisely a MAP solution, the approximation is such that there is no discernible difference in the disclosed implementation (at high code rates, where the amount of puncturing is significant). The actual MAP solution is to not allow any transition from trellis states which would result in a Viterbi decoder outputting a result which is contrary to what a Reed-Solomon decoder has indicated as the desired output.

0061In this contemplated embodiment of the invention, the described approximation functions in part because of an implementation of a four-bit soft-decision Viterbi or third decoder <b>226</b> requiring only five-bit path metrics for minimal implementation loss. For a rate ½ code, two 4-bit symbols are used to form a branch metric, and these in turn are added to a previous path metric to form an updated path metric. The two maximum-scale four-bit inputs (which are forced using the disclosed mapping approach) add up to five bits, and this in turn is added to a previous path metric. So, in this embodiment, as long as the path metric registers saturate, encoder “forcing” is equivalent to forcing the unfavored path metrics to extreme five-bit worse case values, similar to what a MAP processor, having perfect knowledge of a source bit decision, might do.

0062<figref idref="DRAWINGS">FIG. 5</figref> is a schematic diagram of an alternate embodiment of a pipeline communication system according to the present invention. In this embodiment of the invention, a receiver <b>500</b> includes demodulation and decoding elements <b>502</b>-<b>510</b> functioning in a like manner to demodulation and decoding elements <b>202</b>-<b>210</b> of <figref idref="DRAWINGS">FIG. 2</figref>. The receiver <b>500</b> also includes at least one pipeline decoder unit <b>501</b> employing a data interleaver <b>512</b> and a control interleaver <b>514</b> (functioning in a like manner to data interleaver <b>212</b> and control interleaver <b>214</b> described above).

0063In this embodiment of the invention, the outputs of the data interleaver <b>512</b> are provided directly to a Viterbi decoder <b>516</b> as forced a-priori values. The Viterbi decoder <b>516</b> resets selected path metrics in order to force a-priori decision values, in an indirect manner. To be more precise, the Viterbi decoder resets a path metric to an undesirable value if such a path would result in a decision outcome that is contrary to the desired (forced ‘a priori’) outcome. By doing so, undesired outcomes are greatly disfavored during the decoding process. This effectively ‘forces’ desired decoding outcomes, in an indirect manner. The decode status signals provided by the control interleaver <b>214</b> are also passed directly to the Viterbi decoder <b>516</b> to selectively constrain the output of the Viterbi decoder <b>516</b> to be based on either the forced ‘a priori’ values or a delayed version of the demodulated serially concatenated code data provided by delay circuitry <b>518</b>. The output of the Viterbi decoder <b>516</b> is provided to a deinterleaver <b>520</b> and second outer decoder <b>522</b> operating in an analogous manner to deinterleaver <b>228</b> and fourth decoder <b>230</b> of <figref idref="DRAWINGS">FIG. 2</figref>.

0064In one contemplated embodiment of the aforedescribed path resetting technique, applied to a rate 1/n nonsystematic convolutional code, if the number of memory elements in a code is m (resulting in 2^mstates), and it is desired to force a logic level “0” at the output of the third decoder <b>226</b> for a given node, then the top 2^m-1state (path) metrics are not altered, while the bottom 2^m-1state (path) metrics are set to the most unfavorable path metric. In this manner, the next state at the output of the third decoder <b>226</b> will be a logic level “0”. Similarly, to force a logic level “1”, the top 2^m-1state metrics are set to the most unfavorable path metric. This procedure describes the decoding of rate 1/n non-systematic (feedforward shift register-type input) convolutional codes, such as the one illustrated in <figref idref="DRAWINGS">FIG. 3</figref>. As will be appreciated, in this embodiment it is not necessary to reinsert erasures into punctured data positions using this technique. Analogous techniques (e.g., a look-up table to indicate which transitions force logic levels of zeros, and which other transitions force logic levels of ones) using the same concept of selective path metric resetting can be devised for other types of codes (e.g., systematic codes, or rate k/n codes, where k and n are integers larger than one) without departing from the spirit of the invention.

0065Thus, a communication system has been described for accelerating signal decoding and increasing receiver performance in a conventional serial concatenated (convolutional code plus Reed Solomon code) coding environment. The communication system utilizes a pipelined architecture to provide recognizable increases coding gains, even at high data rates, without increasing the speed of decoding elements in pipelined datapaths.

0066As is forthwith demonstrated and described below, similar techniques may be applied to turbo codes having an additional, external code—an external code that might have initially been intended only to detect the presence of decision errors within blocks at the turbo decoder output.

0067<figref idref="DRAWINGS">FIG. 6</figref> is a diagram illustrating a turbo decoder bit error rate (BER) versus energy per source bit (E_b/N_ocharacteristic <b>600</b>. This characteristic <b>600</b> illustrates both a conventional bit error rate floor region <b>630</b> and an improved bit error rate floor region <b>640</b>. The BER of a conventional turbo code <b>610</b> decreases as the energy per source bit increases; however, the rate of BER decrease is qualitatively different, in different E_b/N_oregions. The region of most steep decrease of the conventional turbo code BER characteristic <b>610</b> is commonly referred to as the waterfall region <b>620</b>. The region of relative flattening is commonly referred to as the bit error floor region <b>630</b>. In conventional turbo coders, a conventional BER floor <b>630</b> might be located at a BER of approximately 10⁻⁸. Those having skill in the art will recognize that the BER floor <b>630</b> that approaches approximately 10⁻⁸is simply exemplary of just one embodiment of the invention. The BER may vary anywhere from 10⁻⁴to 10⁻¹⁶, depending on a number of elements and design considerations including the length and type of interleaver, the choice of component codes and code rates, and the modulation being used. However, when employing turbo coding in accordance with the present invention, the BER may be lowered. For example, one might have a BER floor at 10⁻⁹, and desire to push this down to 10⁻¹¹; this invention might aid in realizing this goal.

0068While the qualitative response of the improved BER floor <b>640</b> follows a similar response as the conventional BER floor <b>630</b>, it is clear that the improved BER floor <b>640</b> is significantly lower than the conventional BER floor <b>630</b>. One particular application where high BERs is problematic is within video applications. Many video applications require BERs in the range between 10⁻⁹and 10⁻¹². Many conventional turbo coders simply do not offer these lower BERs using current technology and reasonable interleaver sizes, whereas the present invention offers the promise of lowering the BER of a turbo coder without increasing its interleaver depth. It is within the regions beyond the waterfall region <b>620</b>, where the BER is already very low, but saturates (rather than continuing to drop at a precipitous rate of descent), that use of a conventional turbo decoder is problematic. The present invention addresses, among other things, this deficiency in the conventional turbo decoder art.

0069A convolutional encoder, such as the convolutional encoder of the <figref idref="DRAWINGS">FIG. 3</figref>, can be further improved upon by employing decision forcing to achieve a more effective system. Several examples of methods to perform decision forcing in accordance with the invention are described and shown below.

0070<figref idref="DRAWINGS">FIG. 7A</figref> is a functional diagram illustrating an embodiment of a non-systematic encoder <b>700</b>A operating in accordance with the aforesaid trellis description. The examples shown and described above using the trellis and encoder are suitable as examples to describe various aspects of the invention.

0071Shown within the example of the <figref idref="DRAWINGS">FIG. 7A</figref>, a signal “input,” shown as U, is simultaneously fed to three inputs, a delay block, and two summing junctions (a top summing junction and a bottom summing junction). The two summing junctions are XOR gates and the delay block is a shift register in certain embodiments. The output from the first delay block is fed into both the top summing junction and a second delay block. The output from the second delay block is fed into both the top summing junction and the bottom summing junction. Finally, the output from the top summing junction is shown as output C₁, and the output from the bottom summing junction is shown output C₀. The non-systematic encoder <b>700</b>A depicts just one example of a non-systematic convolutional encoder. Other non-systematic convolutional encoders may also be employed within various embodiments of the invention as well.

0072The code generated by <figref idref="DRAWINGS">FIG. 7A</figref> encoder is illustrative of just one of many such convolutional codes where the principle of path restriction may be applied. Many other convolution codes may be formed, and, during the decoding, certain decoding paths may be “restricted,” without departing from the scope and spirit of the invention. For example, for paths that would not deliver the desired decoding outcome, the path metric for those decoding paths may be set so significantly unfavorable that there is no propagation (during final decision-making) to those paths. In one instance, where an application desires that a most significant bit (MSB) (left-most shift register in the encoder) be path restricted so the paths where the MSB is a 0 be selected in any decision-making, then the path metric for any 1 path may be set to a significantly undesirable (e.g., large) value to attempt to impede any decision based on that path. This method of path restriction in an effort to perform decision forcing is operable within the various embodiments of the invention.

0073While the <figref idref="DRAWINGS">FIG. 7A</figref> illustrates an example of path restriction, the operating principle may be extended to any degree of path restrictions. In some instances, a look up table (LUT) may be used to perform path restriction where multiple bit inputs are received within such a system. That is to say, where there are multi-bit inputs, path restriction can be performed based on any or more of the input bits.

0074<figref idref="DRAWINGS">FIG. 7B</figref> is a functional diagram illustrating an embodiment of a non-systematic code trellis <b>700</b>B that would generated by the encoder illustrated in <figref idref="DRAWINGS">FIG. 7A</figref>. Such a trellis diagram tracks the evolution of states and encoder outputs according to encoder inputs and previous encoder states, as time progresses. Since the encoder in <figref idref="DRAWINGS">FIG. 7A</figref> has two memory elements, the non-systematic code trellis <b>700</b>B possesses four possible states: (00, 01, 10, and 11). Since the encoder of <figref idref="DRAWINGS">FIG. 7A</figref> has one binary input, the trellis diagram possesses two possible inputs: (0,1). Each of the ‘stages’ in the trellis corresponds to an advance in time. For the various transition paths between stages, the notation within <figref idref="DRAWINGS">FIG. 7B</figref> uses a similar notation as that within the <figref idref="DRAWINGS">FIG. 7A</figref> of input bit/output bits being shown by U/C₁C₀. The input to the encoder is the “input bit,” and the output of the convolutional encoder are the “output bits.”

0075Some examples are shown to illustrate the operation of the non-systematic code trellis <b>700</b>B. For example, starting with the 00 state at the top, when a 0 is inputted, the next selected state is again 00, traversing the path designated 0/00. However, when a 1 is inputted, the next selected state is 10, traversing the path designated 1/11. In other words, when a 0 is inputted, the next state of the convolutional encoder is forced into one of the top 2 trellis states; when a 1 is inputted, the next state of the convolutional encoder is forced into one of the bottom two trellis states. Alternatively speaking, when a 0 is inputted, the next encoder state CANNOT BE one of the bottom 2 trellis states; whereas, when a 1 is inputted, the next encoder state CANNOT BE one of the top 2 trellis states.

0076As another example, starting with the 01 state, which is the 2nd to the top state, when a 0 is inputted, the next selected state is 00, traversing the path designated 0/11. However, when a 1 is inputted, the next selected state is 10, traversing the path designated 1/00. In other words, when a 0 is inputted, the next state of the convolutional encoder is forced into one of the top 2 trellis states; when a 1 is inputted, the next state of the convolutional encoder is forced into one of the bottom two trellis states. Alternatively speaking, when a 0 is inputted, the next encoder state CANNOT BE one of the bottom 2 trellis states; whereas, when a 1 is inputted, the next encoder state CANNOT BE one of the top 2 trellis states.

0077One can demonstrate the same results, assuming an initial state of 01, or 11, as well: specifically, when a 0 is inputted, the next encoder state CANNOT BE one of the bottom 2 trellis states; whereas, when a 1 is inputted, the next encoder state CANNOT BE one of the top 2 trellis states.

0078Since convolutional decoding (via either the Viterbi or APP decoding algorithms) is performed by operating upon path metrics, one method to force desired decoding decisions is to make the path metrics associated with the alternative, undesired decision outcomes appear highly unattractive. As the commonality in the CANNOT BE's for previous nonsystematic code illustrate, path transition decisions exhibit a structure that can be exploited. For example, with this code, if one desires to force a ‘0’ decision, the ‘1’ decision can be prohibited by resetting all of the path metrics associated with a transition into the bottom-half states (10 and 11) as undesirable as possible. In other words, if one desires to force a ‘0’ decision in the transition from trellis stage <b>1</b> to trellis stage <b>2</b>, then he need only reset (to ‘undesirable’ figures) the bottom 2 survivor path metrics (which are called ‘state metrics’) of trellis stage <b>2</b>. This way, the top two state metrics of trellis stage <b>2</b> untouched. A similar argument, involving resetting the top two state metrics, is used when a ‘0’ decision is to be prohibited.

0079One can easily show that the above ‘bottom half/top half states’ technique can be applied to any rate 1/n non-recursive (feedforward) convolutional code to force decisions.

0080Below, it is shown how decision forcing may be implemented via path prohibition for an exemplary type of recursive systematic convolutional code. Again, the principles of decision forcing are extendible to other types of recursive systematic convolutional code as well.

0081<figref idref="DRAWINGS">FIG. 8A</figref> is a functional diagram illustrating an embodiment of a recursive systematic encoder <b>800</b>A. The recursive systematic encoder <b>800</b>A is operable to perform the function of the recursive systematic code trellis <b>800</b>B. An input signal, shown as U, is simultaneously fed in two directions. The actual signal of U is passed through directly as output C₁. In addition, the signal U is fed to a summing junction. The output from the summing junction is fed to a delay block from which the output signal C₀is emitted. The output signal C₀is also fed back into the same summing junction as well.

0082As described above with respect to the <figref idref="DRAWINGS">FIG. 7A</figref>, the summing junction is operable to be an XOR gate, and the delay block is a shift register in certain instantiations as shown in the <figref idref="DRAWINGS">FIG. 8B</figref>. The recursive systematic encoder <b>800</b>B shows an example of a single bit input in a recursive systematic encoder. However, it should be known that this is exemplary of the operation of a recursive systematic encoder; extensions to multiple bit inputs do not depart from the scope and spirit of the example, nor the scope and spirit of the application of the invention to data encoded by such encoders.

0083<figref idref="DRAWINGS">FIG. 8B</figref> is a functional diagram illustrating an embodiment of a recursive systematic code trellis <b>800</b>B. The recursive systematic code trellis <b>800</b>B uses two possible inputs (0 and 1) to illustrate its functionality. Again, for the various transition paths between stages, the notation within <figref idref="DRAWINGS">FIG. 8B</figref> uses a similar notation for input bit/output bits as shown by U/C₁C₀. For the first stage, the transitions are as follows:

0084Starting with the 0 state at the top, when a 0 is inputted, the next selected state is again 00, traversing the path designated 0/00. However, when a 1 is inputted, the next selected state is 10, traversing the path designated 1/11.

0085Now starting at the left with the 1 state, when a 0 is inputted, the next selected state is 1, traversing the path 1/11. However, when a 1 is inputted, the next selected state is 0, traversing the path 0/01. For the second stage, the transitions are identical to the first stage, since the state machine dependencies are fully defined by current state and input. Again here in <figref idref="DRAWINGS">FIG. 8B</figref>, as with <figref idref="DRAWINGS">FIG. 7B</figref>, the transitions could continue indefinitely for an indeterminate number of stages.

0086Note that from the trellis diagram of <figref idref="DRAWINGS">FIG. 8B</figref>, ‘0’ inputs leave the encoder in the same state, whereas ‘1’ inputs push the state to cross over to the other state. Therefore, on the decoder side, when one would desire to force a ‘0’ decision, he would prohibit crossover paths. This may be achieved by resetting the path metrics for paths that cross over states to undesirable values. Similarly, when one would desire to force a ‘1’ decision, he would reset path metrics for paths that visit the same state to undesirable values.

0087Recursive systematic encoders different from <figref idref="DRAWINGS">FIG. 8B</figref> might have more complicated trellis descriptions, and more complicated input-to-state path mappings. In fact, <figref idref="DRAWINGS">FIGS. 7A</figref>, <b>7</b>B, <b>8</b>A, and <b>8</b>B are solely illustrative of path restriction techniques that may be performed in accordance with the present invention, and those having skill in the art will recognize that any number of variations, including multi-bit input, multi-state systems, are also operable in accordance with the present invention that utilizes path restriction. In fact, the concept of path restrictions (via path metric resetting) may be used in very general cases, with the aid of a lookup table or algebraic logic (to tell the decoder which path metrics should be reset for a given desired input) without departing from the scope and spirit of the invention.

0088It is noted that most of the previous discussion has concerned itself with decoders which use forward recursions only, such as Viterbi decoders. However, the same techniques may be applied for decoders that use backward recursions—where backward recursion implies that data is processed in the reverse order from which it was received. An important application example is the Log-MAP (more formally known as log—‘A Posteriori Probability’) decoder, which utilizes both forward and backward recursions, and is found in turbo decoding applications. The reason that the same techniques apply is that the forward and backward recursions are each only trying to reproduce the encoding action, and they only differ in the direction in which data is processed. For that reason, for both forward and backward recursions, the state metrics or path metrics which are reset are the same, and the trellis sections at which the resets occur are the same.

0089The operation and methodology of path restriction and/or re-encoding MUXing is extendible, and may be used in various concatenated code applications, as the following descriptions and discussions demonstrate.

0090<figref idref="DRAWINGS">FIG. 9</figref> is a system diagram illustrating an embodiment of a turbo codec <b>900</b> built in accordance with the present invention. The turbo codec <b>900</b> receives an input signal that is fed to an external encoder <b>910</b>. The external encoder <b>910</b> takes a number of sub-blocks of length S bits and adds redundancy to them to create sub-blocks of length S+R bits; collectively, these blocks form a block of length M+N bits. Inside of the external encoder <b>910</b>, in certain embodiments of the invention, is a cyclic redundancy check (CRC) encoder <b>912</b>. The output of the external encoder <b>910</b> is fed to an external code interleaver <b>920</b> that is used in certain embodiments of the invention. The external code interleaver <b>920</b> scrambles the order of the bits within the block that it processes. Note that, in general, the interleaver span is the length of the entire block, rather than a constituent sub-block.

0091Subsequently, the signal is passed to an outer encoder <b>930</b>. Inside of the outer encoder <b>930</b> is an outer convolutional encoder <b>934</b> which would add redundancy to the data, transforming a block of input data of length M+N bits to a block of length M+N+O bits. Since the encoder, in general, would input and output multiple bits at a time (in parallel), a serial to parallel (S/P) converter <b>932</b> and a parallel to serial (P/S) converter <b>936</b> precede and follow the outer convolutional encoder <b>934</b>, when it is necessary to perform the conversion to parallel encoded data to accommodate the outer convolutional encoder <b>934</b>. When the bit stream being fed to the outer encoder <b>930</b> is already in parallel format, the converters <b>932</b> and <b>936</b> are not needed. However, they are shown to illustrate the adaptability of the present invention to accommodate a variety of data streams in various applications.

0092The signal emitted from the outer encoder <b>930</b> is passed to a bit interleaver <b>940</b>. For a block of span N+M+O bits, it would have the same span. The signal is then passed to an inner encoder <b>950</b>. The inner encoder <b>950</b> includes an inner convolutional encoder <b>954</b>, that adds more redundancy to the input data, transforming a block of length M+N+O bits to one of length N+M+O+P bits. The inner encoder is followed by a symbol mapper <b>956</b>, that maps a (multi-) bit description, say, of m bits, to one of 2^mconstellation symbol possibilities. When needed, the inner convolutional encoder <b>954</b> is preceded by a S/P converter <b>952</b>. The inner convolutional encoder <b>954</b> employs a trellis encoder <b>955</b> in certain embodiments of the invention. The trellis encoder <b>955</b> is any number of trellis encoders including those described above in various embodiments of the invention. The signal is then emitted from the inner encoder <b>950</b> and passed to a modulator <b>960</b> before a code symbol is transmitted over a communication channel <b>970</b>. After transmission over the communication channel <b>970</b>, the signal is first de-modulated using a de-modulator <b>980</b> and then passed to a turbo decoder <b>990</b> from which an output signal is emitted.

0093<figref idref="DRAWINGS">FIG. 10A</figref> is a system diagram illustrating an embodiment of a soft in/soft out (SISO) functional block <b>1000</b>A operating built in accordance with the present invention. The SISO functional block <b>1000</b>A employs a SISO block <b>1010</b>A. Two signals C and U are provided as ‘a priori’ signals into the SISO block <b>1020</b>A. After any operations within the SISO block <b>1010</b>A, the two signals are provided as ‘a posteriori’ outputs (estimates with estimate reliabilities) Ĉ and Û. The SISO functional block <b>1010</b>A is exemplary of a four port device, two inputs and two outputs, that is used in various embodiments of the invention.

0094From certain perspectives, the soft in/soft out (SISO) functional block <b>1000</b>A is viewed as being a functional block that is operable to perform decoding of a coded data stream. For example, the two ‘a priori’ signals C and U are coded data streams, and the two ‘a posteriori’ signals Ĉ and Û are decoded data streams. As will be seen in various embodiments of the invention, any number of soft in/soft out (SISO) functional blocks may be concatenated to perform inner and outer decoding of data streams.

0095<figref idref="DRAWINGS">FIG. 10B</figref> is a system diagram illustrating an embodiment of a soft in/soft out (SISO) functional block <b>1000</b>B that generates extrinsic information in accordance with the present invention. The SISO functional clock <b>1000</b>B may be viewed as being a processor, from certain perspectives. The SISO functional block <b>1000</b>B employs a SISO block <b>1010</b>B. Two signals C and U are provided as ‘a priori’ signals into the SISO block <b>1010</b>B. After any operations within the SISO block <b>1010</b>A, the two signals are provided ‘a posteriori’ as outputs Ĉ and Û. Subsequent to being outputs as Ĉ and Û from the SISO block <b>1020</b>B, the original input signals may be subtracted from the outputs Ĉ and Û to generate extrinsic information for C and/or U, respectively. The extrinsic C is viewed as being the resultant of the following equation: extrinsic U=Û−U. Similarly, the extrinsic C is viewed as being the resultant of the following equation: extrinsic C=Ĉ−C. In some 4-port SISO blocks, only one or none of the outputs might be extrinsic outputs; the other could be an ‘a posteriori’ output.

0096The aforesaid SISO input and output signals contain reliability information, which in certain instances, contains more information than simply a logical ‘0’ or ‘1’ that represents a bit. Such information may tell how strongly the signal is actually estimated to be a ‘1’ or ‘0.’

0097A number of soft in/soft out (SISO) functional blocks may be concatenated to perform decoding, e.g., inner and outer decoding, of data streams. When the SISO blocks are concatenated, and selected outputs are fed to another SISO decoder as an input, the relevant SISO output(s) must generate and employ extrinsic data stream(s).

0098The <figref idref="DRAWINGS">FIGS. 11A and 11B</figref> illustrate two different embodiments of serial concatenated code turbo decoders that may also be combined into a third embodiment. That is to say, the two turbo decoders <b>1100</b>A and <b>1100</b>B of the <figref idref="DRAWINGS">FIGS. 11A and 11B</figref> may be combined in a given embodiment, so that two sources of external decoder feedback are possible in a single embodiment.

0099<figref idref="DRAWINGS">FIG. 11A</figref> is a system diagram illustrating an embodiment of a serial concatenated code turbo decoder <b>1100</b>A that feeds back external decoding information (from an external decoder <b>1</b><b>120</b>A) to an outer SISO <b>1114</b>A in accordance with the present invention. The turbo decoder <b>1100</b>A is operable as the turbo decoder <b>990</b> of the <figref idref="DRAWINGS">FIG. 9</figref>, and it is also operable in other embodiments as well. The signal from a de-modulator is provided to an inner SISO block <b>1110</b>A. An inner extrinsic U₁signal is provided to a de-interleaver <b>1112</b>A before being passed to the outer SISO block <b>1114</b>A. An outer extrinsic C_osignal is passed from the outer SISO <b>1114</b>A to an interleaver <b>1116</b>A before being passed as an ‘a priori’ input to the inner SISO <b>110</b>A.

0100An outer Û_osignal is passed from the outer SISO <b>1114</b> to the external decoder <b>1120</b>A. The external decoder <b>1120</b>A includes a hard limiter <b>1122</b>A, an external code deinterleaver <b>1124</b>A, an external (or CRC) decoder <b>1126</b>A, an external code interleaver <b>1127</b>A, and an external code interleaver <b>1128</b>A. The outer Û_osignal is fed to the hard limiter <b>1122</b>A. The output from the hard limiter <b>1122</b>A provides the input for the external (or CRC) decoder <b>1126</b>A. The output from the external (or CRC) decoder <b>1126</b>A provides the input for the external (or CRC) decoder <b>1126</b>A. The external (or CRC) decoder <b>1126</b>A provides decoded bits to the external interleaver code <b>1127</b>A and a correct/incorrect decode indicator for use by the external code interleaver <b>1128</b>A. The outputs from the external code interleaver <b>1127</b>A and the external code interleaver <b>1128</b>A cooperatively operate as the external coding feedback inputs to the outer SISO <b>1114</b>A. They are shown operating cooperatively within the mutual circle to which they join.

0101The output signals (decoded bits, correct decoding indication) from the external decoder <b>1120</b> may be used in multiple ways. In one embodiment, a level-shifted version of the decoded bits may serve as an ‘a priori’ input for the outer SISO <b>1114</b>A (when the external (or CRC) decoder <b>1126</b>A decodes correctly; when it does not, an indeterminate ‘a priori’ indication would be sent to the outer SISO <b>1114</b>A as ‘a priori’ input).

0102In another embodiment, correct decisions may be forced (via any of the previously described techniques for path restrictions) when the external (or CRC) decoder <b>1126</b>A decodes correctly. Any of the explicitly disclosed methods of path restriction may be used, or extensions of path restriction as described within the various embodiments of the invention. This includes applying a path restriction technique to either the forward or backward recursions of the outer SISO <b>1114</b>A, or applying a path restriction technique to both recursions.

0103<figref idref="DRAWINGS">FIG. 11B</figref> is a system diagram illustrating an embodiment of a serial concatenated code turbo decoder <b>1100</b>B that feeds back external decoding information to an inner SISO <b>1110</b>B using a MUX method of decision forcing in accordance with the present invention. The signal from a de-modulator is provided to an inner SISO block <b>1110</b>B. An inner extrinsic U_Isignal is provided to a deinterleaver <b>1112</b>B before being passed to an outer SISO block <b>1114</b>B. An outer extrinsic C_osignal is passed from the outer SISO <b>1114</b>B to an interleaver <b>1116</b>B before being passed as one of the inputs to a multiplexor (MUX) <b>1150</b>B.

0104An outer Û_osignal is passed from the outer SISO <b>1114</b>B to an external decoder <b>1120</b>B. The external decoder <b>1120</b>B includes a hard limiter <b>1122</b>B, an external code deinterleaver <b>1124</b>B, an external (or CRC) decoder <b>1126</b>B, an external code interleaver <b>1127</b>B, and an external code interleaver <b>1128</b>B. The outer Û_osignal is fed to the hard limiter <b>1122</b>B. The output from the hard limiter <b>1122</b>B provides the input for the external (or CRC) decoder <b>1126</b>B. The output from the external (or CRC) decoder <b>1126</b>B provides the input for the external (or CRC) decoder <b>1126</b>B. The external (or CRC) decoder <b>1126</b>B provides decoded bits to the external code interleaver <b>1127</b>B and a correct/incorrect decode indicator for use by the external code interleaver <b>1128</b>B.

0105The external (or CRC) decoder <b>1126</b>B provides a correct/incorrect decode indicator signal to an external code interleaver <b>1128</b>B. The output from the external code interleaver <b>1128</b>B is fed to a validity indicator block <b>1140</b>B. The output from the validity indicator block <b>1140</b>B is passed to an interleaver <b>1141</b>B. The output of the interleaver <b>1141</b>B serves as the input (MUX) line selector for the MUX <b>1150</b>B.

0106The output from the re-outer-encode data block <b>1132</b>B is passed to an interleaver <b>1133</b>B. The output of the interleaver <b>1133</b>B is passed to a block having operations that are performed only if the MUX pass-through of this particular path is enabled. These operations include a maximum reliability shifter <b>1134</b>B and a gain <b>1136</b>B. The output from the interleaver <b>1133</b>B is fed to the maximum reliability shifter <b>1134</b>B, whose output is then passed to the gain <b>1136</b>B. The output from the gain <b>1136</b>B is the other of the inputs provided to the MUX <b>1150</b>B, the other being the output from the interleaver <b>1116</b>B as described above. Again, it is the output of the interleaver <b>1141</b>B that serves as the input (MUX) line selector for the MUX <b>1150</b>B determining which of the two MUX inputs is to be selected.

0107The turbo decoders <b>1100</b>A and <b>1100</b>B of the <figref idref="DRAWINGS">FIGS. 11A and 11B</figref> demonstrate two embodiments of the present invention that may reduce BER floors in applications that benefit from a reduced BER noise floor. Note that an external code feedback technique like that used by the outer decoder of <figref idref="DRAWINGS">FIG. 11A</figref> may be combined with an external code feedback technique like that used by the inner decoder of the <figref idref="DRAWINGS">FIG. 11B</figref>, to cooperatively lower BER floors. There are also other methods in which the present invention is operable to achieve low BER floors using feedback from an external decoder.

0108<figref idref="DRAWINGS">FIG. 12</figref> is a system diagram illustrating an embodiment of a turbo decoder <b>1200</b>, having an inner SISO path restriction (forcing) implementation, that is built in accordance with the present invention. The turbo decoder <b>1200</b> is operable as the turbo decoder <b>990</b> of the <figref idref="DRAWINGS">FIG. 9</figref>, although it is also operable in other embodiments. The signal from a de-modulator is provided to an inner SISO block <b>1210</b>. An inner extrinsic U_Isignal is provided to a de-interleaver <b>1212</b> before being passed to an outer SISO block <b>1214</b>. An outer extrinsic C_osignal is passed from the outer SISO <b>1214</b> to an interleaver <b>1216</b> before being passed back as an input to the inner SISO block <b>1210</b>.

0109An outer Û_osignal is passed from the outer SISO <b>1214</b> to an external decoder <b>1220</b>. The external decoder <b>1220</b> includes a hard limiter <b>1222</b>, an (optional) external code de-interleaver <b>1224</b>, an external or CRC decoder <b>1226</b>, and (optional) external code interleavers <b>1227</b> and <b>1228</b>.

0110The outer Û_osignal is fed to the hard limiter <b>1222</b>. The output from the hard limiter <b>1222</b> provides the input for the (optional) external code de-interleaver <b>1224</b>. The output from the (optional) external code de-interleaver <b>1224</b> is used as the input for the external (or CRC) decoder <b>1226</b>. The external (or CRC) decoder <b>1226</b> provides decoded bits to the (optional) external code interleaver <b>1227</b> and a correct/incorrect decode indicator for use by the (optional) external code interleaver <b>1228</b>.

0111The output signals (decoded bits, correct decoding indication) from the external (or CRC) decoder <b>1226</b> are provided to a validity indicator block <b>1240</b> and a re-encode data block <b>1230</b>. The correct decoding indication from the external (or CRC) decoder <b>1226</b> may pass through the (optional) external code interleaver <b>1227</b> before getting to the re-encode data block <b>1230</b>. The decoded bits from the external (or CRC) decoder <b>1226</b> may pass through the (optional) external code interleaver <b>1228</b> before getting to the validity indicator block <b>1240</b>.

0112The output from the validity indicator block <b>1240</b> is passed to a (turbo decoder) interleaver <b>1242</b>. The output from the re-outer-encode data block <b>1230</b> is passed to an interleaver <b>1232</b>. The outputs of the interleaver <b>1232</b> and the (turbo decoder) interleaver <b>1242</b> are used as the controller and trigger of the inner SISO <b>1210</b>, respectively, as they are shown operating cooperatively within the mutual circle to which they join. The turbo decoder <b>1200</b>, having a path restriction (decision forcing) implementation, shows yet another embodiment of the present invention that is operable to achieve BER floors approaching those required for video applications and other applications that benefit from a greatly reduced BER noise floor. Again, as mentioned above, there are many different ways to perform path restriction, some of which have been explicitly described in the preceding text. Other extendible methods to perform path restriction are also included within the scope and spirit of the invention.

0113Note that a external code feedback technique like that used by the outer decoder of <figref idref="DRAWINGS">FIG. 11A</figref> may be combined with an external code feedback technique like that used by the inner decoder of 12, to cooperatively lower BER floors.

0114<figref idref="DRAWINGS">FIG. 13</figref> is a system diagram illustrating an embodiment of a parallel concatenation encoder <b>1300</b> built in accordance with the present invention. An external encoder <b>1310</b>, that may be a CRC encoder <b>1311</b> in certain embodiments of the invention, provides its output to an (optional) external interleaver <b>1320</b>. The output of the (optional) external interleaver <b>1320</b>, which is labeled as U, serves as one of the ultimate outputs of the parallel concatenation encoder <b>1300</b>, namely, as C₂=U. The same output from the (optional) external interleaver <b>1320</b> is also provided to a redundancy generator block <b>1330</b> from which is output another of the ultimate outputs of the parallel concatenation encoder <b>1300</b>, namely, as C₁. In addition, the same output from the (optional) external interleaver <b>1320</b> is also provided to an interleaver <b>1340</b> and subsequently to a redundancy generator block <b>1332</b> from which is output the last of the ultimate outputs of the parallel concatenation encoder <b>1300</b>, namely, C₀. The parallel concatenation encoder <b>1300</b> shows one possible embodiment of a parallel concatenation encoder that operates in accordance with the present invention. Other embodiments of parallel concatenation encoders may also be constructed without departing from the scope and spirit of the invention.

0115<figref idref="DRAWINGS">FIG. 14</figref> is a system diagram illustrating an embodiment of a parallel concatenation decoder <b>1400</b> built in accordance with the present invention. In certain embodiments of the invention, the output signals C₂, C₁and C₀of the parallel concatenation encoder <b>1300</b> shown in <figref idref="DRAWINGS">FIG. 13</figref> are the inputs to the parallel concatenation decoder <b>1400</b>. The SISO blocks shown in the <figref idref="DRAWINGS">FIG. 14</figref> may be viewed as five port devices, having three “C” inputs and two “U” inputs each.

0116Input signals C₂and C₁are provided to a SISO block <b>1</b><b>1410</b>. The C₂signal is also passed to an interleaver <b>1420</b>. The output from the interleaver <b>1420</b>, C_2-int, is passed as an input to a SISO block <b>2</b><b>1440</b>. An input signal C₀is also fed into the SISO block <b>2</b><b>1440</b>.

0117The U₁output from the SISO block <b>1</b><b>1410</b> is passed to a summing junction where the ‘a priori’ U₁input to the SISO block <b>1</b><b>1410</b> is subtracted from it to generate an extrinsic U₁signal. The extrinsic U₁signal is passed to interleaver <b>1430</b> whose output is then passed to both another summing junction and also as the ‘a priori’ input to SISO block <b>2</b><b>1440</b>, shown as signal U_1-int. The “U” output of the SISO block <b>2</b><b>1440</b>, shown as U₂, is summed with the negative of the output of the interleaver <b>1430</b>, U_1-int, to generate an extrinsic U₂signal. The extrinsic U₂signal is passed to a de-interleaver <b>1450</b>, and the output from the de-interleaver <b>1450</b> is passed back as the ‘a priori’ U₁input to the SISO block <b>1</b><b>1410</b>.

0118Before the output signal from the SISO block <b>2</b><b>1440</b>, shown as U₂, is summed with the negative of the output of the interleaver <b>1430</b> to generate an extrinsic U₂signal, a portion of this signal is fed to a deinterleaver <b>1460</b> to generate the decoder output signal Û.

0119<figref idref="DRAWINGS">FIG. 15</figref> is a functional diagram illustrating a parallel concatenation code application <b>1500</b> operating in a decision forcing, or path restriction, implementation in accordance with the present invention. The parallel concatenation feedback <b>1500</b> is operable with or without an external deinterleaver and interleaver blocks. Such blocks would be necessary if an external interleaver were used in the encoding processing. To simplify further discussion, we shall illustrate the case where external interleaving is not used in the encoding process. It is understood that the simpler case illustrated herein is exemplary, and that many other embodiments, including those employing external deinterleaving, may be achieved without departing from the scope and spirit of the invention.

0120An input signal shown as Û is fed into hard limiter <b>1522</b>. The output from the hard limiter <b>1522</b> is fed external decoder <b>1526</b>. In this embodiment, it is noted that a external code could represent many different types of block-based codes, including a CRC code, Reed Solomon or BCH block code, a Hamming code, or a Parity Check Code, among others. Moreover, this external code may be primarily intended and used for error detection and/or error correction code. The identifying feature of this external code is that it is a block code, and as such, its data span is confined to a block length, and also that the decoder should be able to indicate whether the block that has been decoded has actually been correctly decoded—with a high degree of reliability.

0121The external decoder <b>1526</b> has two outputs. These outputs are both its decoded bits and information indicating whether the external code block was successfully decoded—i.e., decoded with no errors. This information is shown as the success/fail for block output signal emitting from the external decoder <b>1526</b>. It is also noted that, in the application described herein, the size of an external block is generally shorter than the size of a turbo decoder block (whose span is defined by the length of the turbo encoder's interleaver). Therefore, external code error detection functions are typically repeated on several blocks to cover all of the bits in a longer, turbo code block.

0122The ‘successful decoding’ output of external decoder <b>1526</b> may be interpreted as ‘forcing information,’ regarding whether or not to force particular bit decisions (within the turbo decoder). The other, ‘bit decisions’ output of external decoder <b>1526</b> contains ‘instructions,’ in other words, the actual values that may that may (or may not) be forced within the turbo decoder.

0123As an example, when the parallel concatenation code application <b>1500</b> of the <figref idref="DRAWINGS">FIG. 15</figref> is applied to embodiments of the invention operable as shown in the <figref idref="DRAWINGS">FIG. 14</figref>, the instructions and forcing information are then fed to the SISO <b>1</b> block <b>1410</b>, where the path forcing restrictions would be imposed. Alternatively, (but usually, with less BER floor lowering effect) the instructions and forcing information may be passed through interleaving blocks (to reassemble them in the proper order) and then be fed to the SISO block <b>2</b><b>1440</b> to implement instantiated decision forcing via path restriction.

0124<figref idref="DRAWINGS">FIG. 16</figref> is a functional diagram illustrating a parallel concatenation code application <b>1600</b> with feedback operating in an overloading implementation in accordance with the present invention. This particular embodiment is based on the assumption that an external interleaver was not used in the encoding process. However, it is clear that the invention is operable within situations where one may be used as well. Again, it is understood that the simpler case illustrated herein is exemplary, and that many other embodiments, including those employing external interleaving, may be achieved without departing from the scope and spirit of the invention.

0125An input signal shown as e_Û is fed as one of the inputs to a multiplexor (MUX) <b>1650</b>. An input signal shown as is fed into a hard limiter <b>1622</b>. The output from the hard limiter <b>1622</b> is fed into an external decoder <b>1626</b>. The external decoder <b>1626</b> may be a CRC decoder in certain embodiments of the invention. Decoded bits, provided by the external decoder <b>1626</b>, are passed through a gain <b>1636</b> whose output is provided as the other of the inputs of the MUX <b>1650</b>.

0126One output of external decoder <b>1626</b> includes information of a decision of success or fail for a block on which the parallel concatenation feedback <b>1600</b> operates. This output from external decoder <b>1626</b> serves as the selector of MUX <b>1650</b> to determine which of the output from gain <b>1636</b> or the input signal shown as Û is to be used as an output that is fed back to the inner SISO within the parallel concatenation feedback <b>1600</b>.

0127<figref idref="DRAWINGS">FIG. 17</figref> is a functional flow chart illustrating an embodiment of a turbo decoder method <b>1700</b> performed in accordance with the present invention. In a chart item <b>1710</b>, an identification is made when an external code sub-block has been decoded correctly. The external code sub-block is a cyclic redundancy check (CRC) block in certain embodiments of the invention. Then, in a chart item <b>1720</b>, a high confidence level is assigned to bits from any correctly decoded external code sub-block. In chart item <b>1730</b>, the bits from a correctly decoded external code sub-block are fed back to the turbo decoder as inputs with decision emphasis. The emphasized decisions of bits from the correctly decoded external code sub-block will tend to influence many other bit decisions in subsequent decoding iterations.

0128The turbo decoder method <b>1700</b> is operable when the external decoder's correct decisions are fed back to an outer SISO in a serially concatenated code application, or the ‘second’ SISO (that operates on source bit interleaved data) in a parallel concatenated code application. The technique may also involve external deinterleaving and external interleaving between sub-blocks of the external code bits in other embodiments as well.

0129<figref idref="DRAWINGS">FIG. 18</figref> is a functional flow chart illustrating another embodiment of a turbo decoder method <b>1800</b> performed in accordance with the present invention. In a chart item <b>1810</b>, an identification is made when a external code sub-block has been decoded correctly. Again, the external code sub-block is a cyclic redundancy check (CRC) block in certain embodiments of the invention. In a chart item <b>1820</b>, a high confidence level is assigned to the bits derived from any correctly decoded external code sub-block. In chart item <b>1830</b>, bits of high confidence derived from one or more correctly decoded external code sub-blocks is scattered (via interleaving) throughout a turbo code frame, that is typically larger-than a sub-block. Then, in a chart item <b>1840</b>, one or more subsequent decoding iterations(s) are performed, with decision emphasis applied to the high confidence bits derived from correctly decoded external code sub-blocks.

0130The fact that the high confidence bits from a correctly decoded external code sub-block are scattered throughout the turbo decoded frame can improve decoder BER performance in subsequent iterative passes in the decoding process. The turbo decoder method <b>1800</b> is operable when the external decoder's correct decisions are fed back to an inner SISO in a serial concatenated turbo code application, or to the first decoder (which does not have source bit interleaving) in a parallel concatenated code application. The technique may also involve external deinterleaving and external interleaving in certain embodiments as well.

0131It is also noted that, in general, external decoding and external decoding feedback as previously described may be performed at any (or all) iteration stages within the turbo decoding process.

0132While various embodiments of the invention have been described, it will be apparent to those of ordinary skill in the art that many more embodiments and implementations are possible that are within the scope of this invention.