Patent Publication Number: US-2016233888-A1

Title: Turbo decoding techniques

Description:
CROSS-REFERENCE TO RELATED APPLICATION(S) 
     This patent application claims the benefit of U.S. Provisional Patent Application No. 61/802,038, filed on Mar. 15, 2013. The entire content of the before-mentioned provisional patent application is incorporated by reference herein. 
    
    
     TECHNICAL FIELD 
     This document relates to digital communication. 
     BACKGROUND 
     Many modern digital communication systems use orthogonal frequency division multiplexing (OFDM) modulation technology. Various types of error correction codes are used to increase robustness of transmitted signals. For example, OFDM and error coding is used in wireless technologies such as Long Term Evolution (LTE) and wired communication technologies such as digital subscriber line (DSL). 
     SUMMARY 
     This document describes technologies, among other things, for turbo decoding of OFDM modulation signals. In some implementations, a combined turbo decoding and turbo equalization technique may be used. 
     In one aspect, methods, systems and apparatus for turbo decoding including serially concatenated TCM and Reed Solomon block codes, with convolutional interleaving, are disclosed. 
     In another aspect, methods, systems and apparatus for turbo decoding of serially concatenated TCM and Reed Solomon block codes, with convolutional interleaving, using constellations of variable sizes as part of the same code block are disclosed. Where the least significant bits of constellations are both block coded and trellis coded, and the most significant bits are block coded only. 
     In another aspect disclosed techniques provide for a buffer for constellations from more than one OFDM symbol, which provides for turbo decoding of convolutional interleaving over more than one OFDM symbol is disclosed. Alternatively, this buffer may be after the SISO constellation demapper, for demapped constellations. 
     In another aspect, a SISO synchronization buffer for the block coded only bits from the SISO constellation demapper is disclosed. The buffer also accepts the bits from the SISO trellis decoder and assembles them into bytes. 
     In another aspect, a turbo decoder comprising a feedback path, and a SISO data frame buffer for one or more data frames is disclosed. 
     In another aspect, the disclosed data reception techniques use a constellation demapper and mapper that supports variable size constellations. 
     These and other aspects, and their implementations and variations are set forth in the drawings, the description and the claims. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  illustrates a digital subscriber loop (DSL) transmitter and receiver with non-iterative decoder. 
         FIG. 2  illustrates an encoder for parallel concatenated convolutional codes. 
         FIG. 3  illustrates an encoder for serially concatenated trellis coded modulation (TCM) and block codes. 
         FIG. 4  illustrates a trellis encoder having a convolutional encoder and bit convertor. 
         FIG. 5  illustrates a generalized triangular interleaver. 
         FIG. 6  depicts various constellations used in digital communications. 
         FIG. 7  illustrates a turbo decoder for parallel concatenated convolutional codes. 
         FIG. 8  illustrates a turbo decoder for serially concatenated TCM and block codes. 
         FIG. 9  is a block diagram representation of turbo decoder used in a DSL receiver. 
         FIG. 10  is a flowchart representation of turbo decoding for DSL control. 
         FIG. 11  is a block diagram representation of a pipelined decoding module for DSL. 
         FIG. 12  is a flowchart representation of a process of turbo decoding and turbo equalization. 
     
    
    
     Like reference symbols in the various drawings indicate like elements. 
     DETAILED DESCRIPTION 
     Techniques for turbo decoding and turbo equalization of received signals to produce data bits are disclosed. In the description, the following abbreviations are used. 
     ADSL=Asymmetric Digital Subscriber Line 
     AFE=Analog Front End 
     ASIC=Application Specific Integrated Circuit 
     BPSK=Binary Phase Shift Keying 
     DSL=Digital Subscriber Line 
     EPROM=Erasable Programmable Read Only Memory 
     EEPROM=Electrically Erasable Programmable Read Only Memory 
     FEQ=Frequency Domain Equalizer 
     FFT=Fast Fourier Transform 
     FPGA=Field Programmable Gate Array 
     IEEE=Institute of Electrical and Electronics Engineers 
     IFFT=Inverse Fast Fourier Transform 
     ITU=International Telecommunications Union 
     LLR=Log Likelihood Ratio 
     LSBs=Least Significant Bits 
     MAP=Maximum a Posteriori 
     MSBs=Most Significant Bits 
     n-QAM=Quadrature Amplitude Modulation 
     n-QPSK=Quadrature Phase Shift Keying 
     OFDM=Orthogonal Frequency Division Multiplexing 
     PAR=Peak to Average Ratio 
     SISO=Soft Input Soft Output 
     SOVA=Soft Output Viterbi Algorithm 
     TCM=Trellis Coded Modulation 
     VDSL=Very High Speed Digital Subscriber Line 
     The International Telecommunications Union (ITU) standards for Asymmetric Digital Subscriber Line (ADSL) and Very High Speed Digital Subscriber Line (VDSL) transceivers specify an error correcting code consisting of concatenated trellis coded modulation (TCM) and Reed Solomon block codes, with convolutional interleaving. The standards also specify Orthogonal Frequency Division Multiplexing (OFDM) for modulation and demodulation. OFDM is a multicarrier technique, which uses an Inverse Fast Fourier Transform (IFFT) for modulation and a Fast Fourier Transform (FFT) for demodulation. The sizes of the signal constellations in the frequency bins of the IFFT and FFT (i.e. assigned to each of the carriers) are variable. And the least significant bits of the constellations are both block coded and trellis coded, while the most significant bits are block coded only. 
     Turbo decoding significantly improves the coding gain of error correcting codes. Turbo decoding is the iterative decoding of concatenated codes. It was originally designed for parallel concatenated convolutional codes, and has been extended to serially concatenated convolutional codes, concatenated trellis coded modulation, and concatenated trellis coded modulation and block codes. 
     Present day receivers compatible with the ADSL and VDSL standards have done a single decoding; they have not been able to decode iteratively. In some embodiments, their coding gain would be improved by being able to turbo decode concatenated TCM and Reed Solomon block codes, with convolutional interleaving, using OFDM with variable size constellations. 
       FIG. 1  depicts a block diagram example of a DSL transmitter and a DSL receiver with a non-iterative decoder. Conventional decoding of the concatenated code in the ADSL and VDSL standards uses a single pass, non-iterative, decoder. A soft input constellation demapper precedes the decoder. The inputs to the constellation demapper are constellation points, which each represent from one to fifteen bits, and how many bits each constellation represents. The outputs are encoded bits. The outputs for the two least significant bits (which are both block coded and trellis coded) are soft outputs (i.e. 0 and 1 with reliability information.) And the outputs for the thirteen most significant bits (which are block coded only) are hard outputs (i.e. 0 and 1.) The soft outputs from the constellation demapper go to a soft input hard output Viterbi decoder. The hard outputs from the Viterbi decoder, and from the constellation demapper, go to a synchronization buffer. Which delays the outputs from the constellation demapper, to account for the latency of the Viterbi decoder, and assembles the bits into bytes. The bytes from the synchronization buffer go to convolutional deinterleaver. The deinterleaved bytes become the codewords input to a hard input hard output Reed Solomon decoder. Some hard output Reed Solomon decoders, while using hard information at the bit level, can use soft information at the byte level for errors and erasures decoding. 
     Conventional techniques for turbo decoding of concatenated trellis coded modulation and block codes has been for a fixed size constellation, with all of the bits of the constellation being both block coded and trellis coded.  FIG. 2  illustrates an encoder for parallel concatenated convolutional codes.  FIG. 3  illustrates an encoder for serially concatenated trellis coded modulation (TCM) and block codes.  FIG. 4  illustrates a trellis encoder having a convolutional encoder and a bit convertor. 
     As an alternative to turbo decoding the code in the ADSL and VDSL standards, there have been proposals to add different types of codes to the standards, for which there is prior art for iterative decoding. There have been proposals to add parallel concatenated convolutional codes, parallel concatenated convolutional codes with trellis coded modulation, and low density parity check codes. 
     Turbo Decoding of Serially Concatenated TCM and Reed Solomon Block Codes, with Convolutional Interleaving 
     In some embodiments, turbo decoding of serially concatenated TCM and Reed Solomon block codes, with convolutional interleaving, using constellations of variable sizes as part of the same code block may be performed. The least significant bits of constellations are both block coded and trellis coded, and the most significant bits are block coded only. 
     A buffer may be provided for constellations from more than one OFDM symbol. The buffer provides for turbo decoding of convolutional interleaving over more than one OFDM symbol. Alternatively, this buffer may be after the SISO constellation demapper, for demapped constellations. 
     A SISO synchronization buffer may be configured for the block coded only bits from the SISO constellation demapper and may also accept the bits from the SISO trellis decoder, and output of the soft synchronization buffer, and assemble them into bytes. 
     In the turbo decoder feedback path, a SISO data frame buffer may be provided for buffering for one or more data frames. 
     In some embodiments, a turbo decoder supports, or decoders, the serially concatenated TCM and Reed Solomon block coding, with convolutional interleaving, in the ADSL and VDSL standards. It supports variable sized constellations (see, e.g.,  FIG. 6 ), where the least significant bits are both block coded and trellis coded, and the most significant bits are block coded only. And convolutional interleaving over multiple OFDM time domain symbols. 
     In some embodiments, a turbo decoder includes modules for turbo decoding the error correcting code in the standards, including: A buffer for constellations from more than one OFDM symbol. A SISO constellation demapper. A SISO trellis decoder. A SISO synchronization buffer. A SISO convolutional deinterleaver. A SISO Reed Solomon decoder. A SISO convolutional deinterleaver. A SISO data frame buffer. 
     ADSL and VDSL are multicarrier systems which use an Inverse Fast Fourier Transform (IFFT) for modulation, and a Fast Fourier Transform (FFT) for demodulation. Each of the frequency bins of the IFFT and FFT contains a point in a signal constellation. Where each constellation point is a point in the Euclidean plane, described by a complex number, Z=X+jY, which represents modulated data. And for hard data, X and Y are odd integers. The constellations may be of variable sizes, i.e. each constellation point may represent from 1 to 15 bits. I.e. the modulation for each frequency bin can range from BPSK to 32K QAM. Some frequency bins may be unused, and represent 0 bits. A table stores the number of data bits for each frequency bin (subcarrier) from f=0 to the highest transmitted frequency bin. n data bits are mapped to one of 2̂n constellation points. 
     The Reed Solomon coding used by the ADSL and VDSL standards is a conventional byte based Reed Solomon code with its operations in Galois Field GF(2 8 ). Where the number of message bytes is k, the number of parity bytes r, and the number of codeword bytes n=k+r. 
     The message polynomial is m(x)=m 0 x k-1 +m 1 x k-2 + . . . +m k-2 x+m k-1 . 
     The parity polynomial is p(x)=p 0 x r-1 +p 1 x r-2 + . . . +p r-2 x+p r-1 . 
     The generator polynomial is g(x)=(x+a)(x+a 2 )(x+a 3 ) . . . (x+a r ). 
     The codeword is c(x)=m(x)x r +p(x). 
     And p(x)=m(x)x r  mod g(x). 
       FIG. 5  illustrates a generalized triangular interleaver. The convolutional interleaver used by the ADSL and VDSL standards is a generalized triangular interleaver. The bytes of the Reed Solomon codewords are delayed by an amount that varies linearly with the byte index i. Byte B i  is delayed by (D−1)×i bytes, where D is the interleaver depth. And (D−1)=M×K. Where K is the interleaver block length (or number of delay lines), and M is a nonnegative integer number of bytes. 
     Referring again to  FIG. 4 , the trellis coding used by the ADSL and VDSL standards is Wei&#39;s 4D 16 state code. Bits u 2  . . . u 1  are input to a recursive systematic convolutional encoder of rate ⅔, which outputs bits u 2  . . . u 0 . Bits u 3  . . . u 0  are input to a bit converter with equations v 1 =u 1 +u 3 , v 0 =u 3 , w 1 =u 0 +u 1 +u 2 +u 3 , w 0 =u 2 +u 3 . Bits v 1  . . . v 0 , and w 1  . . . w 0  become the two least significant bits input to the constellation mapper on alternate mappings. 
     With reference to  FIG. 9 , in some embodiments, the received time domain DSL signal is filtered, and may be equalized in the time domain. The cyclic extension is removed from the filtered and equalized signal, giving a time domain signal whose length matches that of the modulating IFFT. An FFT transforms the time domain signal to points in signal constellations in the frequency domain. Giving one constellation point for each used frequency bin. The constellation points go to a Frequency Domain Equalizer (FEQ), which does one complex multiplication of each constellation point, to correct amplitude and phase. 
     The equalized constellation points go to a constellations buffer for the constellation points from more than one OFDM symbol. The constellations buffer is large enough for the extent of the convolutional interleaving, as extrinsic information is fed back from Reed Solomon codeword bytes that may have been interleaved over more than one OFDM symbol. In some embodiments, the structure of the constellations buffer is a sliding window or shift register type of structure. Then a parallel to serial converter outputs the constellation points to a SISO constellation demapper. Alternatively demapped constellations could be buffered. 
     The SISO constellation demapper has two inputs: Constellation points which represent from one to fifteen bits. And the number of bits that each constellation represents. A bits table stores the number of bits carried by each frequency bin. It outputs encoded data for soft decoding. For error correcting codes, soft inputs and outputs refer to data bits represented as a log likelihood ratio (LLR). Where for data bit d, LLR(d)=log (Pr(d=1)/Pr(d=0)), or an approximation. The SISO constellation demapper may also accept extrinsic information which has been re-encoded and re-mapped by a SISO constellation mapper. 
     Decoders may output LLRs calculated exactly by the MAP algorithm, or approximately using the concept of a concurrent path (for trellis decoders) or concurrent codeword (for block decoders). Call the received codeword R, the set of soft received bits r n . And D the hard decoded codeword, with minimum Euclidean distance to R, and bits d n . Call C n  the concurrent codeword, with minimum Euclidean distance to R, and c n =˜d n . Then approximations used include: LLR n ≈d n ×((R−C n )−(R−D)). And LLR n ≈d n ×((R−C n ) 2 −(R−D) 2 )/4. 
     All of the encoded bits are Reed Solomon block coded, and interleaved. The least significant bits are also trellis coded, and go to a SISO trellis decoder. For two to fifteen bit constellations, the two least significant bits are trellis coded, for one bit constellations, one bit is trellis coded. 
     The notation L(;;) n  is used to refer to the log likelihood ratios of bits of iteration n. Where the first parameter refers to the code: i for the inner code, and o for the outer code. The second parameter refers to the decoders: i for the input, o for the output, e for extrinsic information, and a for a priori information. And the third parameter is optional, and refers to the range of bits: m for most significant bits (MSBs), and l for least significant bits (LSBs). 
       FIG. 10  is a flowchart representation of turbo decoding for DSL control.  FIG. 11  is a block diagram representation of a pipelined decoding module for DSL. The SISO trellis decoder has two inputs. The 2 LSBs from the SISO constellation demapper are the received encoded bits input to the SISO trellis decoder. And 3 bits of a priori information are input to the SISO trellis decoder. For the first iteration the a priori information=0. For subsequent iterations, the a priori information is 3 soft bits extracted from the SISO data frame buffer (which are 3 decoded bits), which correspond to 4 encoded LSBs from the SISO constellation demapper, i.e., 2 encoded LSBs from two successive constellations. The a priori information to the inner decoder L(i;a) is the buffered 3 least significant bits of the interleaved extrinsic information from the previous iteration of the outer decoder, ˜L(o;e). With L(i;o) the output of the inner decoder, and the inner extrinsic information, L(i;e)=L(i:o)−L(i;a). 
     With reference to  FIG. 7  and  FIG. 8 , in some embodiments, the algorithms for the SISO trellis decoding are the logarithmic version of the Maximum a Posteriori algorithm (log MAP), and the Soft Output Viterbi Algorithm (SOVA). Both perform exhaustive searches of the trellis, and are practical for a 16 state code. Both the log MAP, and SOVA algorithm have versions which use forward and backward passes, or are forward only with a sliding window. The trellis code used in the ADSL and VDSL standards is Wei&#39;s 4-dimensional, 16 state trellis code, which places specific requirements on the decoder. The log MAP algorithm uses additions in place of multiplications in the MAP algorithm, and the maxlog MAP algorithm has been shown to be equivalent to the Soft Output Viterbi Algorithm. At low E b /N 0  ratios, the log MAP algorithm may outperform the SOVA by up to 0.7 dB. 
     Referring to  FIG. 10  and  FIG. 11 , the extrinsic information from the inner decoder L(i;e), and the interleaved msbs to the outer decoder&#39;s input ˜L(o;i;m) are input to the SISO synchronization buffer. The SISO synchronization buffer is used to synchronize the MSBs from the SISO constellation demapper, which are block coded only, with the inner extrinsic information from the SISO trellis decoder, L(i;e), which has a decoding latency. Note that constellations of 3 or more bits have msbs. After synchronization, the soft bits are assembled into soft bytes. The soft bytes from the SISO synchronization buffer go to a convolutional deinterleaver. The deinterleaved soft bytes are the codewords, L(o;i), input to the outer SISO Reed Solomon decoder. 
     Next, SISO decoding of the outer Reed Solomon code is performed. With L(o;i) the systematic input to the decoder, and L(o;o) the output of the decoder, the outer extrinsic information is L(o;e)=L(o;o)−L(o;i). 
     The log MAP and SOVA algorithms are currently impractical for decoding Reed Solomon codes. Some other possible methods of SISO Reed Solomon decoding include: Reliability assisted hard decision decoding algorithms, including Chase type algorithms. Algebraic list decoding algorithms, including the Koetter and Vardy algorithm. Ordered statistics decoding, including the box and match algorithm, and iterative decoding algorithms. 
     The outer extrinsic information L(o;e), from the SISO Reed Solomon decoder, is fed back to a SISO convolutional interleaver, giving ˜L(o;e), and then to a SISO data frame buffer. With a convolutional interleaver the interleaved outer extrinsic information is calculated from bits that are in three stages of decoding: Bits that have completed decoding by the outer decoder. Bit that are being decoded by the outer decoder. Bits for which an outer codeword has not yet been deinterleaved, and have extrinsic information that equals zero. 
     The interleaved outer extrinsic information may extend over more than one OFDM symbol. Constellations from one or more OFDM symbols are read from the constellations buffer, and input to the SISO constellations demapper, in synchronization with their a priori information. 
     Decoding iterations continue through SISO trellis decoding, SISO synchronization, deinterleaving, and SISO Reed Solomon decoding. 
     Iterative decoding is considered to have converged when the SISO decoders agree on the output (outputs match). The number of iterations is typically greater than or equal to two, and less than or equal to sixty four, after which hard bits can be output as the decoded data. In some embodiments, a hard output algebraic Reed Solomon decoder may also be incorporated, and hard bits output when it indicates a successful decoding. 
     The turbo architecture for iterative decoding uses one of each of the decoding blocks, and feedback. A pipelined architecture (which is analogous to loop unrolling) is an alternative. With reference to  FIG. 11 , a pipelined architecture contains multiple decoding modules, typically one module for each decoding iteration. In the pipelined architecture for decoding DSL, a decoding module contains: A SISO trellis decoder. A SISO synchronization buffer. A convolutional deinterleaver. A SISO Reed Solomon decoder. A convolutional interleaver. A SISO data frame buffer. 
     In some embodiments, the decoding modules are connected serially. With the inputs to each module being the output of the SISO constellation demapper, and the a priori information from the previous module&#39;s SISO data frame buffer. The outputs being the a priori information from the SISO data frame buffer, and hard bits from the SISO Reed Solomon decoder. The a priori information to the first module is set to zero. 
     The pipelined architecture decoding modules may also each contain a SISO constellation demapper, and SISO constellation mapper. In which case they would accept constellations as inputs, rather than the output of the SISO constellation demapper. 
       FIG. 12  is a flowchart representations of a process  2100  for turbo decoding for DSL. At  2102 , in a synchronization buffer, encoded data from a constellation demapper and trellis decoder is received. At  2104 , an output of the synchronization buffer is convolutionally deinterleaved. At  2106 , the deinterleaved output of the synchronization buffer is decoded. At  2108 , soft or hard decoded bits are generated from the deinterleaved output. 
     It will be appreciated that techniques are disclosed for turbo decoding OFDM symbols. It will further be appreciated that techniques for combined turbo decoding and equalization are disclosed. The disclosed techniques can be implemented in receivers that receive wired or wireless OFDM signals and produce data and control bits by decoding the received signals. 
     The disclosed and other embodiments and the functional operations and modules described in this document can be implemented in digital electronic circuitry, or in computer software, firmware, or hardware, including the structures disclosed in this document and their structural equivalents, or in combinations of one or more of them. The disclosed and other embodiments can be implemented as one or more computer program products, i.e., one or more modules of computer program instructions encoded on a computer readable medium for execution by, or to control the operation of, data processing apparatus. The computer readable medium can be a machine-readable storage device, a machine-readable storage substrate, a memory device, a composition of matter effecting a machine-readable propagated signal, or a combination of one or more them. The term “data processing apparatus” encompasses all apparatus, devices, and machines for processing data, including by way of example a programmable processor, a computer, or multiple processors or computers. The apparatus can include, in addition to hardware, code that creates an execution environment for the computer program in question, e.g., code that constitutes processor firmware, a protocol stack, a database management system, an operating system, or a combination of one or more of them. A propagated signal is an artificially generated signal, e.g., a machine-generated electrical, optical, or electromagnetic signal, that is generated to encode information for transmission to suitable receiver apparatus. 
     A computer program (also known as a program, software, software application, script, or code) can be written in any form of programming language, including compiled or interpreted languages, and it can be deployed in any form, including as a stand alone program or as a module, component, subroutine, or other unit suitable for use in a computing environment. A computer program does not necessarily correspond to a file in a file system. A program can be stored in a portion of a file that holds other programs or data (e.g., one or more scripts stored in a markup language document), in a single file dedicated to the program in question, or in multiple coordinated files (e.g., files that store one or more modules, sub programs, or portions of code). A computer program can be deployed to be executed on one computer or on multiple computers that are located at one site or distributed across multiple sites and interconnected by a communication network. 
     The processes and logic flows described in this document can be performed by one or more programmable processors executing one or more computer programs to perform functions by operating on input data and generating output. The processes and logic flows can also be performed by, and apparatus can also be implemented as, special purpose logic circuitry, e.g., an FPGA (field programmable gate array) or an ASIC (application specific integrated circuit). 
     Processors suitable for the execution of a computer program include, by way of example, both general and special purpose microprocessors, and any one or more processors of any kind of digital computer. Generally, a processor will receive instructions and data from a read only memory or a random access memory or both. The essential elements of a computer are a processor for performing instructions and one or more memory devices for storing instructions and data. Generally, a computer will also include, or be operatively coupled to receive data from or transfer data to, or both, one or more mass storage devices for storing data, e.g., magnetic, magneto optical disks, or optical disks. However, a computer need not have such devices. Computer readable media suitable for storing computer program instructions and data include all forms of nonvolatile memory, media and memory devices, including by way of example semiconductor memory devices, e.g., EPROM, EEPROM, and flash memory devices; magnetic disks, e.g., internal hard disks or removable disks; magneto optical disks; and CD ROM and DVD-ROM disks. The processor and the memory can be supplemented by, or incorporated in, special purpose logic circuitry. 
     While this document contains many specifics, these should not be construed as limitations on the scope of an invention that is claimed or of what may be claimed, but rather as descriptions of features specific to particular embodiments. Certain features that are described in this document in the context of separate embodiments can also be implemented in combination in a single embodiment. Conversely, various features that are described in the context of a single embodiment can also be implemented in multiple embodiments separately or in any suitable sub-combination. Moreover, although features may be described above as acting in certain combinations and even initially claimed as such, one or more features from a claimed combination can in some cases be excised from the combination, and the claimed combination may be directed to a sub-combination or a variation of a sub-combination. Similarly, while operations are depicted in the drawings in a particular order, this should not be understood as requiring that such operations be performed in the particular order shown or in sequential order, or that all illustrated operations be performed, to achieve desirable results. 
     Only a few examples and implementations are disclosed. Variations, modifications, and enhancements to the described examples and implementations and other implementations can be made based on what is disclosed.