Systems and methods for advanced iterative decoding and channel estimation of concatenated coding systems

• US 9,191,256 B2
• Filed: 12/03/2012
• Issued: 11/17/2015
• Est. Priority Date: 12/03/2012
• Status: Expired due to Fees

• Current Assignee: Ln2 Db LLC
• Original Assignee: Digital PowerRadio, LLC
• Inventors: Vojcic, Branimir R, Shayegh, Farnaz, Dogan, Hakan, Lee, Wookwon
• Primary Examiner(s): Ahn, Sam K
• Assistant Examiner(s): Murillo Garcia, Fabricio R
• Application Number:
  US13/693,023
• Publication Number:
  US 20140153625A1
• Time in Patent Office: 1,079 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1625 in communications, e.g. transmission, interfaces
• CPC Class Codes: H03M 13/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
• CPC Class Codes: H03M 13/1108 Hard decision decoding, e.g. bit flipping, modified or weighted bit flipping
• CPC Class Codes: H03M 13/1111 Soft-decision decoding, e.g. by means of message passing or belief propagation algorithms
• CPC Class Codes: H03M 13/112 with correction functions for the min-sum rule, e.g. using an offset or a scaling factor
• CPC Class Codes: H03M 13/1131 Scheduling of bit node or check node processing
• CPC Class Codes: H03M 13/114 Shuffled, staggered, layered or turbo decoding schedules
• CPC Class Codes: H03M 13/1154 Low-density parity-check convolutional codes [LDPC-CC]
• CPC Class Codes: H03M 13/1191 Codes on graphs other than LDPC codes
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/23 using convolutional codes, e.g. unit memory codes
• CPC Class Codes: H03M 13/255 with Low Density Parity Check [LDPC] codes
• CPC Class Codes: H03M 13/27 using interleaving techniques
• CPC Class Codes: H03M 13/2792 Interleaver wherein interleaving is performed jointly with another technique such as puncturing, multiplexing or routing
• CPC Class Codes: H03M 13/2906 using block codes H03M13/2957 takes precedence
• CPC Class Codes: H03M 13/2933 using a block and a convolutional code H03M13/2957 takes precedence
• CPC Class Codes: H03M 13/2948 Iterative decoding H03M13/2957 takes precedence
• CPC Class Codes: H03M 13/3707 Adaptive decoding and hybrid decoding, e.g. decoding methods or techniques providing more than one decoding algorithm for one code
• CPC Class Codes: H03M 13/373 with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes
• CPC Class Codes: H03M 13/3746 with iterative decoding
• CPC Class Codes: H03M 13/3784 : for soft-output decoding of block codes
• CPC Class Codes: H03M 13/3938 : Tail-biting H03M13/2996 takes precedence
• CPC Class Codes: H03M 13/45 : Soft decoding, i.e. using symbol reliability information H03M13/41 takes precedence
• CPC Class Codes: H03M 13/451 : using a set of candidate code words, e.g. ordered statistics decoding [OSD]
• CPC Class Codes: H03M 13/453 : wherein the candidate code words are obtained by an algebraic decoder, e.g. Chase decoding
• CPC Class Codes: H03M 13/612 : Aspects specific to channel or signal-to-noise ratio estimation H03M13/63 takes precedence
• CPC Class Codes: H03M 13/616 : Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations
• CPC Class Codes: H03M 13/6325 : Error control coding in combination with demodulation
• CPC Class Codes: H03M 13/6337 : Error control coding in combination with channel estimation
• CPC Class Codes: H03M 13/6362 : by puncturing
• CPC Class Codes: H03M 13/6541 : DVB-H and DVB-M
• CPC Class Codes: H03M 13/6552 : DVB-T2
• CPC Class Codes: H03M 13/658 : Scaling by multiplication or division
• CPC Class Codes: H04B 17/309 : Measuring or estimating channel quality parameters
• CPC Class Codes: H04L 1/004 : by using forward error control H04L1/0618 takes precedence; coding, decoding or code conversion, for error detection or correction H03M13/00
• CPC Class Codes: H04L 1/0045 : Arrangements at the receiver end
• CPC Class Codes: H04L 1/005 : Iterative decoding, including iteration between signal detection and decoding operation
• CPC Class Codes: H04L 1/0057 : Block codes H04L1/0061, H04L1/0064 take precedence
• CPC Class Codes: H04L 1/0059 : Convolutional codes
• CPC Class Codes: H04L 1/0065 : Serial concatenated codes
• CPC Class Codes: H04L 1/0071 : Use of interleaving interleaving per se H03M13/27
• CPC Class Codes: H04L 25/022 : of frequency response
• CPC Class Codes: H04L 25/0222 : Estimation of channel variability, e.g. coherence bandwidth, coherence time, fading frequency
• CPC Class Codes: H04L 25/0224 : using sounding signals
• CPC Class Codes: H04L 25/0236 : using estimation of the other symbols
• CPC Class Codes: H04L 27/261 : Details of reference signals
• CPC Class Codes: H04L 27/2649 : Demodulators

Abstract

Systems and methods for decoding block and concatenated codes are provided. These include advanced iterative decoding techniques based on belief propagation algorithms, with particular advantages when applied to codes having higher density parity check matrices. Improvements are also provided for performing channel state information estimation including the use of optimum filter lengths based on channel selectivity and adaptive decision-directed channel estimation. These improvements enhance the performance of various communication systems and consumer electronics. Particular improvements are also provided for decoding HD Radio signals, including enhanced decoding of reference subcarriers based on soft-diversity combining, joint enhanced channel state information estimation, as well as iterative soft-input soft-output and list decoding of convolutional codes and Reed-Solomon codes. These and other improvements enhance the decoding of different logical channels in HD Radio systems.

Claims

1. A method for iteratively decoding a hybrid digital radio signal, the signal being an Orthogonal Frequency-Division Multiplexed (OFDM) signal comprising OFDM reference subcarriers, OFDM data subcarriers, and OFDM symbol intervals, the method comprising:

a. performing, by a demodulator and by a de-mapper, OFDM demodulation and subcarrier de-mapping of the hybrid digital radio signal into system control and data sequences symbols to obtain, by a control data decoder, received distorted modulated symbols;

b. performing, by a channel estimator, initial channel state information estimation based on the received distorted modulated symbols, from the control data decoder, wherein said received distorted modulated symbols are carried by a plurality of OFDM data subcarriers and a plurality of OFDM reference subcarriers in at least one OFDM symbol interval;

c. performing, by the channel estimator, phase correction of the received distorted modulated symbols based on the initial channel state information estimation into coherent demodulated signals;

d. performing, by a symbol-to-bit demapper, symbol-to-bit demapping of the coherent demodulated signals by calculating log-likelihood ratios of the system control and data sequences symbols;

e. producing, by a de-interleaver and demultiplexer, one or more logical channel signals by de-interleaving and demultiplexing the log-likelihood ratios of the system control and data sequences symbols;

f. processing the one or more logical channel signals by producing, by a decoder, soft estimates of convolutional code coded bits using soft-input soft-output decoding of one or more convolutional codes associated with the one or more logical channels, wherein the soft-input soft-output decoding of the one or more convolutional codes comprises depuncturing one or more convolutional coded bit sequences;

g. calculating, by the channel estimator, improved channel state information by performing at least one additional iteration of channel state information estimation based on at least some of said soft convolutional code coded bits estimates; and

h. performing, by a convolutional decoder, enhanced convolutional decoding of at least one of a Program Service Data (PSD) Protocol Data Unit (PDU), a Primary In-Band On-Channel Data Service (PIDS) PDU, audio packet data, a Main Program Service (MPS) PDU header and an Advanced Application Service (AAS) PDU using said improved channel state information.

2. The method of claim 1 wherein the initial channel state information estimation comprises:

a. identifying symbols of the received distorted modulated symbols that are known pilot symbols and unknown symbols belonging to the reference subcarriers, and unknown data symbols belonging to the data subcarriers;

b. estimating the unknown symbols;

c. selecting a smoothing filter for time and frequency domain channel estimation;

d. selecting filter lengths of said smoothing filter based on estimated time selectivity and frequency selectivity of said channel response wherein said time selectivity and frequency selectivity are estimated by using the known pilot symbols and at least one of the estimated unknown symbols;

e. applying said selected smoothing filter to said received distorted modulated symbols;

f. estimating the channel response of said filtered distorted modulated symbols, the estimation based on said using said known pilot symbols, estimated unknown symbols and a first set of unknown data symbols, the first set of unknown data symbols being selected as a fraction of the unknown data symbols having more reliability than the remaining fraction of the unknown data symbols; and

g. with respect to symbol positions corresponding to said remaining fraction of the unknown data symbols, estimating the channel response by interpolation based on the estimated values of channel response obtained from said known pilot symbols, estimated unknown symbols and said first set of unknown data symbols.

3. The method of claim 2 wherein estimating unknown symbols comprises:

a. soft diversity combining of the system control data sequence symbols that carry the same symbol values;

b. differentially decoding said soft diversity combined symbols to obtain a corresponding soft decoded control data sequence of bits; and

c. reconstructing control data sequence symbols from said decoded control data sequence bits.

4. The method of claim 2 wherein estimating unknown symbols comprises:

a. soft diversity combining of the system control data sequence symbols that carry the same symbol values;

b. differentially decoding said soft diversity combined symbols to obtain a corresponding soft decoded control data sequence of bits;

c. decoding said soft decoded control data sequence bits to obtain improved decoded control data sequence bits using single parity check code bits wherein

d. the soft decoded control data sequence bit comprises a parity bit protected field of two or more bits, and upon determining that the parity does not check, flipping a least reliable soft decoded control data sequence bit in said parity bit protected field

e. ; and

f. reconstructing control data sequence symbols from said improved decoded control data sequence bits.

5. The method of claim 1 wherein said at least one additional iteration of channel state information estimation comprises:

estimating a channel response,

selecting a smoothing filter for time and frequency domain channel estimation,

selecting filter lengths of said smoothing filter based on estimated time selectivity or frequency selectivity of said channel response.

6. The method of claim 5 wherein at least one of the filter lengths selected during said additional iteration of channel state information estimation is shorter than at least one of the estimation filter lengths used in the initial channel state information estimation.

7. The method of claim 1 wherein said soft estimates of convolutional code coded bits are log-likelihood ratios of said convolutional code coded bits.

8. The method of claim 1 wherein said soft-input soft-output decoding of said one or more convolutional codes is based on a tail-biting Log-MAP algorithm.

9. The method of claim 1 wherein said soft-input soft-output decoding of said one or more convolutional codes is based on a tail-biting Max-Log-MAP algorithm.

10. The method of claim 1 wherein said enhanced decoding of at least one of said PSD PDU, PIDS PDU and audio packet data comprises at least one list soft-input soft-output convolutional decoding and soft-input soft-output Cyclic Redundancy Check (CRC) decoding, and wherein the list soft-input soft-output convolutional decoding produces a sequence of soft convolutional code information bits and a list that includes at least some of most likely sequences of hard decisions of convolutional code information bits.

11. The method of claim 10 wherein said list soft-input soft-output convolutional decoding is selected from the group consisting of:

a. list Log-MAP decoding;

b. list Max-Log-MAP decoding; and

c. list soft-output Viterbi decoding.

12. The method of claim 1 wherein enhanced decoding of a MPS PDU header comprises:

a. soft-input soft-output decoding of the convolutional code carrying said MPS PDU header to produce soft information bits outputs of the convolutional code;

b. upon determining that hard decisions of said soft information bits outputs of the convolutional code do not correspond to a codeword of a Reed-Solomon code, soft-input soft-output Reed-Solomon decoding of said soft information bits outputs of the convolutional code, and

c. upon determining that hard decisions of said soft information bits outputs of the convolutional code correspond to a codeword of a Reed-Solomon code, using hard decisions of said soft information bits output of the convolutional code as a decoded MPS PDU header without using soft-input soft-output Reed-Solomon decoding.

13. The method of claim 12 further including processing of soft information bits of the convolutional code before decoding by the soft-input soft-output Reed-Solomon decoder, the processing comprising:

a. upon determining there are no detected errors in the MPS PDU header in the previous frame, improving estimates of said soft information bits outputs of the convolutional code corresponding to the MPS PDU header by comparing at least one fields of the MPS PDU header in the present frame with at least one field of the MPS PDU header in one or more previous frames, such that said information bits outputs of the convolutional code corresponding to the present MPS PDU header are determined based on the corresponding convolutional code information bits of the MPS PDU header in the previous frame;

e-r and

b. improving estimates of said soft information bits outputs of the convolutional code corresponding to audio packet locator fields of the MPS PDU header by comparing values of consecutive audio packet locator fields of the MPS PDU header.

14. The method of claim 12 wherein soft-input soft-output decoding of said Reed-Solomon code operates on log-likelihood ratios of said information bits outputs of the convolutional code using message passing, the method further comprising:

a. generating P>

1 binary parity check matrices with at least 64 sparse columns wherein up to 64 sparse columns contain only a single entry equal to 1 per column, wherein sparse columns of each of P parity check matrices correspond to different subsets of up to 64 bit log-likelihood ratios of 64+R least reliable bit log-likelihood ratios;

b. iteratively decoding said log-likelihood ratios using said P parity check matrices with sparse columns to produce updated log-likelihood ratios, the number of iterations of said decoding based on one of a predetermined number of iterations and a determination that at least one of said P matrices produces a valid codeword; and

c. upon determining that decoding using said P parity check matrices produces no valid codeword, performing additional decoding based at least in part on algebraic decoding of the sequences of said updated log-likelihood ratios.

15. The method of claim 12 wherein soft-input soft-output decoding of said Reed-Solomon code comprises simple greedy scheduling of check equation updates, for at least M equations, 1<

M≦

64, during an iteration in decoding of the Reed-Solomon code represented by a parity check matrix with at least 64 parity check rows and at least 768 columns, the method further comprising;

a. For the set of M′

≦

M of non-updated check nodes out of M check nodes of the parity check matrix, calculating values Val_i=Min₁+Min₂, I=1, . . . , L, where 1≦

L≦

M′ and

where Min₁ and Min₂ are the two smallest values in the set of absolute values of variable-to-check messages {|Mvc(i,;

)|} where index i corresponds to the set of non-updated check nodes;

b. sorting the set {Val_i} calculated in step a in decreasing order as ordering vector I={I₁, I₂ . . . I_L} such that I₁ is the index of a check node with largest value Val, 1₂ is the index of a check node with the next largest value Val and I_L is the index of a check node with the smallest value Val;

c. updating L check node equations according to the ordering vector, I={I₁, I₂ . . . I_L} calculated in step b, by calculating and propagating corresponding check-to-variable messages and updating variable-to-check messages for all variables that received check-to-variable messages in this step; and

d. repeating steps a, b and c until all check nodes are updated by calculating and propagating corresponding check-to-variable messages.

16. The method of claim 12 wherein the soft-input soft-output decoding of said Reed-Solomon code operates on log-likelihood ratios of information bits outputs of the convolutional code using message passing, and for at least one variable node, comprises:

a. calculating a check-to-variable message Mcv(i,j) from check node i to variable node j;

b. identifying two smallest absolute values, Min₁, and Min₂, in a set of variable-to-check messages Mvc(i, k), where k≠

j, excluding the message from variable j to check node i, Mvc(i,j);

c. calculating the scaling factor α

=1−

β

·

Min₁/Min₂, where β

is a non-negative number such that 0≦

β

≦

1; and

d. scaling the check-to-variable message Mcv(i,j) as Mcv(i,j)=α

·

Mcv(i,j).

17. The method of claim 12, wherein hard decision sequences of soft information bits outputs of the convolutional code for enhanced decoding of a MPS PDU header determine whether a codeword corresponds to a Reed-Solomon (96,88) code.

18. The method of claim 1 wherein enhanced decoding of a MPS PDU header comprises:

a. list soft-input soft-output decoding of the convolutional code carrying said MPS PDU header to produce a sequence of soft convolutional code information bits and a list that includes at least some of most likely sequences of hard decisions of information bits outputs of the convolutional code;

b. upon determining that any of hard decision sequences of said soft information bits outputs of the convolutional code do not correspond to a codeword of a Reed-Solomon code, soft-input soft-output Reed-Solomon decoding of said soft information bits outputs of the convolutional code; and

c. upon determining that a hard decision sequence of said soft information bits outputs of the convolutional code corresponds to a codeword of a Reed-Solomon code, using said hard decision sequence as a decoded MPS PDU header.

19. The method of claim 18 wherein said soft convolutional code information bits are processed before processing by the soft-input soft-output Reed-Solomon decoder, the processing comprising:

a. upon determining there were no detected errors in the MPS PDU header in the previous frame, improving estimates of some said soft information bits outputs of the convolutional code corresponding to the MPS PDU header by comparing at least one fields of the MPS PDU header in the present frame with at least one field of the MPS PDU header in one or more previous frames, such that said information bits outputs of the convolutional code corresponding to the present MPS PDU header are determined based on the corresponding convolutional code information bits of the MPS PDU header in the previous frame; and

b. improving estimates of said soft information bits outputs of the convolutional code corresponding to audio packet locator fields of the MPS PDU header by comparing values of consecutive audio packet locator fields of the MPS PDU header.

20. The method of claim 18 wherein soft-input soft-output decoding of said Reed-Solomon code operates on log-likelihood ratios of information bits of the convolutional code using message passing and comprises:

a. generating P>

1 binary parity check matrices with at least 64 sparse columns wherein up to 64 sparse columns contain only a single entry equal to 1 per column, wherein sparse columns of each of P parity check matrices correspond to different subsets of up to 64 bit log-likelihood ratios of 64+R least reliable bit log-likelihood ratios;

b. iteratively decoding said log-likelihood ratios using said P parity check matrices with sparse columns to produce updated log-likelihood ratios, the number of iterations of said decoding based on one of a predetermined number of iterations and a determination that at least one of said P matrices produces a valid codeword; and

c. upon determining that decoding using said P parity check matrices produces no valid codeword, performing additional decoding that b based at least in part on algebraic decoding of the sequences of said updated log-likelihood ratios.

21. The method of claim 18 wherein soft-input soft-output decoding of said Reed-Solomon code comprises simple greedy scheduling of check equation updates, for at least M equations, 1<

M≦

64, during an iteration in decoding of the Reed-Solomon code represented by a parity check matrix with at least 64 parity check rows and at least 768 columns, the method further comprising;

a. for the set of M′

≦

M of non-updated check nodes out of M check nodes of the parity check matrix, calculating values Val_i=Min₁+Min₂, i=1, . . . , L, where 1≦

L≦

M′ and

where Min₁ and Min₂ are the two smallest values in the set of absolute values of variable-to-check messages {|Mvc(i,;

)|} where index i corresponds to the set of non-updated check nodes;

b. sorting the calculated set {Val_i} in decreasing order as an ordering vector I={I₁, I₂ . . . I_L} such that I₁ is the index of a check node with largest value Val, I₂ is the index of a check node with the next largest value Val and I_L is the index of a check node with the smallest value Val;

c. updating L check node equations according to the ordering vector, I={I₁, I₂, . . . , I_L}, calculated in step b, by calculating and propagating corresponding check-to-variable messages and updating variable-to-check messages for all variables that received check-to-variable messages in this step; and

d. repeating steps a, b and c until all check nodes are updated by calculating and propagating corresponding check-to-variable messages.

22. The method of claim 18 wherein the soft-input soft-output decoding of said Reed-Solomon code operates on log-likelihood ratios of information bits of the convolutional code using message passing and for at least one variable node comprises:

a. calculating a check-to-variable message Mcv(i,j) from check node i to variable node j;

b. identifying two smallest absolute values, Min₁, and Min₂, in a set of variable-to-check messages Mvc(i, k), where k≠

j, excluding the message from variable j to check node i, Mvc(i,j);

c. calculating the scaling factor α

=1−

β

·

Min₁/Min₂, where β

is a non-negative number such that 0≦

β

≦

1; and

d. scaling the check-to-variable message Mcv(i,j) as Mcv(i,j)=α

·

Mcv(i, j).

23. The method of claim 18, wherein hard decision sequences of soft information bits outputs of the convolutional code for enhanced decoding of a MPS PDU header determine whether a codeword corresponds to a Reed-Solomon (96,88) code.

24. The method of claim 1 wherein enhanced decoding of AAS PDU comprises:

a. one of a soft-input soft-output tail-biting decoding of a convolutional code and a list soft-input soft-output tail-biting decoding of a convolutional code; and

b. soft-input soft-output decoding of a Reed-Solomon code.

25. The method of claim 24 wherein said soft-input soft-output decoding of said Reed-Solomon code operates on log-likelihood ratios of information bits outputs of the convolutional code using message passing and comprises:

a. generating P>

1 binary parity check matrices with at least 256 sparse columns wherein up to 256 sparse columns contain only a single entry equal to 1 per column, wherein sparse columns of each of P parity check matrices correspond to different subsets of up to 256 bit log-likelihood ratios of 256+R least reliable bit log-likelihood ratios;

b. iteratively decoding of said log-likelihood ratios using said P parity check matrices with sparse columns to produce updated log-likelihood ratios, the number of iterations of said decoding based on one of a predetermined number of iterations and a determination that at least one of said P matrices produces a valid codeword; and

c. upon determining that decoding using said P parity check matrices produces no valid codeword, performing additional decoding based at least in part on algebraic decoding of the sequences of said updated log-likelihood ratios.

26. The method of claim 24 wherein said soft-input soft-output decoding of said Reed-Solomon code comprises simple greedy scheduling of check equation updates, for at least M equations, where 1<

M≦

256, during an iteration in decoding of the Reed-Solomon code represented by a parity check matrix with at least 256 parity check rows and at least 2040 columns, the method further comprising;

a. for the set of M′

≦

M of non-updated check nodes out of M check nodes of the parity check matrix, calculating values Val_i=Min₁+Min₂, i=1, . . . , L, where 1≦

L≦

M′ and

where Min_i and Min₂ are the two smallest values in the set of absolute values of variable-to-check messages {|Mvc(i,;

)|} where index i corresponds to the set of non-updated check nodes;

b. sorting the calculated set {Val_i} in decreasing order as an ordering vector I={I_i, I₂, . . . I_L}, such that I₁ is the index of a check node with largest value Val, I₂ is the index of a check node with the next largest value Val and I_L is the index of a check node with the smallest value Val;

c. updating L check node equations according to the ordering vector, I={I₁, I₂, . . . , I_L} calculated in step b, by calculating and propagating corresponding check-to-variable messages and updating variable-to-check messages for all variables that received check-to-variable messages in this step; and

d. repeating steps a, b and c until all check nodes are updated by calculating and propagating corresponding check-to-variable messages.

27. The method of claim 24 wherein the soft-input soft-output decoding of said Reed-Solomon code operates on log-likelihood ratios of information bits of the convolutional code using message passing, and for at least one variable node, comprises:

a. calculating a check-to-variable message Mcv(i,j) from check node i to variable node j;

b. identifying two smallest absolute values, Min₁ and Min₂, in a set of variable-to-check messages Mvc(i, k), where k≠

j, excluding the message from variable j to check node i, Mvc(i,j);

c. calculating the scaling factor α

=1−

β

·

Min₁/Min₂, where β

is a non-negative number such that 0≦

β

≦

1; and

d. scaling the check-to-variable message Mcv(i,j) as Mcv(i,j)=α

·

Mcv(i,j).

28. The method of claim 24, wherein the code for enhanced decoding of a AAS PDU header corresponds to a Reed-Solomon (255,223) code.