Methods, apparatus, and systems for coding with constrained interleaving

• US 20150039964A1
• Filed: 08/02/2013
• Published: 02/05/2015
• Est. Priority Date: 09/10/2010
• Status: Active Grant

• Current Assignee: Eric M. Dowling, John P. Fonseka
• Original Assignee: Trellis Phase Communications, LP
• Inventors: Fonseka, John P., Dowling, Eric Morgan
• Granted Patent: US 9,240,808 B2
• Time in Patent Office: Days
• US Class Current: 714/756
• CPC Class Codes: H03M 13/098 using single parity bit
• CPC Class Codes: H03M 13/1102 Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
• CPC Class Codes: H03M 13/1148 Structural properties of the code parity-check or generator matrix
• CPC Class Codes: H03M 13/1154 Low-density parity-check convolutional codes [LDPC-CC]
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/152 Bose-Chaudhuri-Hocquenghem [BCH] codes
• CPC Class Codes: H03M 13/253 with concatenated codes
• CPC Class Codes: H03M 13/255 with Low Density Parity Check [LDPC] codes
• CPC Class Codes: H03M 13/256 with trellis coding, e.g. with convolutional codes and TCM
• CPC Class Codes: H03M 13/271 Row-column interleaver with permutations, e.g. block interleaving with inter-row, inter-column, intra-row or intra-column permutations
• CPC Class Codes: H03M 13/2742 Irregular interleaver wherein the permutation pattern is not obtained by a computation rule, e.g. interleaver based on random generators
• CPC Class Codes: H03M 13/275 Interleaver wherein the permutation pattern is obtained using a congruential operation of the type y=ax+b modulo c
• 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/2909 Product codes
• CPC Class Codes: H03M 13/2918 with error correction codes in three or more dimensions, e.g. 3-dimensional product code where the bits are arranged in a cube
• CPC Class Codes: H03M 13/2927 Decoding strategies
• CPC Class Codes: H03M 13/2933 using a block and a convolutional code H03M13/2957 takes precedence
• CPC Class Codes: H03M 13/2945 using at least three error correction codes H03M13/2957 takes precedence
• CPC Class Codes: H03M 13/2948 Iterative decoding H03M13/2957 takes precedence
• CPC Class Codes: H03M 13/3746 : with iterative decoding
• CPC Class Codes: H03M 13/4115 : list output Viterbi decoding
• CPC Class Codes: H03M 13/6331 : Error control coding in combination with equalisation
• CPC Class Codes: H04L 1/0041 : Arrangements at the transmitter end

Abstract

Serially-concatenated codes are formed in accordance with the present invention using a constrained interleaver. The constrained interleaver cause the minimum distance of the serial concatenated code to increase above the minimum distance of the inner code alone by adding a constraint that forces some or all of the distance of the outer code onto the serially-concatenated code. This allows the serially-concatenated code to be jointly optimized in terms of both minimum distance and error coefficient to provide significant performance advantages. Constrained interleaving can be summarized in that it: 1) uses an outer code that is a block code or a non-recursive convolutional code, and as such, there are multiple codewords present in the constrained interleaver, 2) selects a desired MHD, 3) selects an interleaver size and a set of predefined interleaver constraints to prevent undesired (low-distance) error events so as to achieve the desired MHD, and 4) performs uniform interleaving among the allowable (non-constrained) positions, to thereby maximize or otherwise improve the interleaver gain subject to the constraints imposed to maintain the desired MHD.

Claims

1-17. -17. (canceled)

18. A communications apparatus comprising:

a constrained interleaver configured to rearrange an ordering of a sequence of N=rm input bits in accordance with a permutation function in order to produce a permuted sequence of output bits, wherein N, r, and m are positive integers, m>

1, and the rearrangement of the ordering in accordance with the permutation function is equivalent to performing the following operations;

applying a word-level pseudo-random permutation function to pseudo-randomly rearrange an ordering of a plurality of multi-bit words embedded in the sequence of N=rm input bits;

loading the N=rm number of input bits into a r×

m array of bits, wherein the array has r rows and m columns, and the bits are serially loaded into the r×

m array of bits along rows,

applying an i^th pseudo-random row permutation function to each row i, for i=1, 2, . . . r, wherein the i^th pseudo-random row permutation function pseudo-randomly rearranges an ordering of m bits in the i^th row, wherein a number of ways that the i^th respective pseudo-random permutation function can pseudo-randomly rearrange the m bits in the i^th row is restricted in accordance with at least one inter-row constraint; and

reading bits out of the r×

m array along r-bit columns to form the permuted sequence of output bits.

19. The communications apparatus of claim 18, wherein m=ρ

n, where ρ and

n are positive integers, and each multi-bit word corresponds to an n-bit word, whereby there are ρ

number of n-bit words per row.

20. The communications apparatus of claim 18, wherein each multi-bit word corresponds to a multi-bit codeword associated with a corresponding component code that is a member of the group consisting of a common component code and a selected one of a plurality of component codes.

21. The communications apparatus of claim 18, wherein the at least one inter-row constraint restricts the i^th respective pseudo-random permutation function in accordance with how coded bits are already placed by a second pseudo-random permutation function corresponding to a second row different from the i^th row.

22. The communications apparatus of claim 21, wherein the at least one inter-row constraint ensures that coded bits of any codeword on the i^th row can share no more than a pre-defined integer, k(l), number of columns with coded bits of any codeword placed on the (i−

l)^th row, where l=1, 2, . . . l_max, where l is a positive integer representative of a row offset and l_max is a positive integer representative of a maximum row offset to which the inter-row constraint will be applied.

23. The communications apparatus of claim 22, wherein the inter-row constraint is configured to interpret the integer (i−

l) in a cyclic fashion in accordance with a modulo r integer arithmetic.

24. The communications apparatus of claim 18, wherein the serially loaded into the r×

m array of bits along rows corresponds to a row-major order.

25. The communications apparatus of claim 18, wherein the reading bits out of the r×

m array along r-bit columns corresponds to a column-major order.

26. The communications apparatus of claim 18, wherein the reading bits out of the r×

m array along r-bit columns is performed from top to bottom in each r-bit column during the reading of the bits out of the r×

m array.

27. The communications apparatus of claim 18, wherein each of the permutation function, the word-level pseudo-random permutation, and the i^th pseudo-random row permutation function, for i=1, 2, . . . r correspond to a respective pseudo randomization that is predetermined prior to a runtime, wherein the runtime corresponds to a time when the constrained interleaver performs the rearrangement of the ordering in accordance with the permutation function.

28. The communications apparatus of claim 27, further comprising:

at least one vector of pointers configured for use, at the runtime, to facilitate the rearrangement of the ordering in accordance with the permutation function.

29. The communications apparatus of claim 28, wherein the at least one vector of pointers is used to facilitate table lookup operations.

30. The communications apparatus of claim 18, the communication apparatus further comprising:

an outer encoder configured to transform a sequence of input bits to the sequence of N=rm input bits, wherein the sequence of N=rm input bits is encoded in accordance with an outer code, and the outer code is a member of the group consisting of a block code, a Low Density Parity Check (LDPC) code, a convolutional code transformed to a block code, and a non-recursive convolutional code; and

an inner encoder configured to transform the permuted sequence of output bits to a sequence of inner-encoded bits, wherein the sequence of inner-encoded bits is encoded in accordance with an inner recursive convolutional code (IRCC), whereby the sequence of inner-encoded bits constitutes a serially-concatenated sequence of bits that incorporates coding from both the inner code and the outer code in accordance with a serially-concatenated code that has a minimum Hamming distance of d_sc;

wherein the outer code has a minimum Hamming distance of d_o and the inner code has a minimum Hamming distance of d_i;

wherein the integer r is selected to be large enough to enforce d_sc>

d₀d_i.

31. The communications apparatus of claim 30, wherein the communications apparatus is a member of the group consisting of a headend system configured to communicate with a plurality of user devices, a user device configured to communicate with the headend system, a peer-to-peer communication device, an optical communications device, an optical communications device configured to support a backbone link, an optical communications device configured to support backbone Internet traffic, a cellular communications headend system, a cellular mobile communications device, and a mobile user data enabled communications device.

32. The communications apparatus of claim 30, wherein the convolutional code transformed to a block code includes one or more termination bits.

33. The communications apparatus of claim 30, wherein the one or more termination bits comprises a complete set of termination bits, whereby the convolutional code transformed to a block code is an equivalent block code where the convolutional code is terminated.

34. The communications apparatus of claim 30, wherein the outer code is a block code and the block code is a non-binary code which is a member of the group consisting of a BCH code and a Reed-Solomon (RS) code.

35. The communications apparatus of claim 30, further comprising:

a signal mapper configured to map the sequence of inner-encoded bits to a transmission signal, wherein the signal mapper is a member of the group consisting of a stateless signal mapper and a state-based modulator.

36. The communications apparatus of claim 30, further comprising:

a signal mapper configured to map a sequence of encoded bits to a transmission signal, wherein the signal mapper is a member of the group consisting of a stateless signal mapper and a state-based modulator, wherein the encoded bits include coding from at least both the inner encoder and the outer encoder.

37. The communications apparatus of claim 18, the communication apparatus further comprising:

an outer encoder configured to transform a sequence of input bits to the sequence of N=rm input bits, wherein the sequence of N=rm input bits is encoded in accordance with an outer code, and the outer code is a member of the group consisting of a block code, a Low Density Parity Check (LDPC) code, a convolutional code transformed to a block code, and a non-recursive convolutional code; and

a BICM (Bit-Interleaved Coded Modulation) mapper configured to receive as input the permuted sequence of output bits, wherein the BICM mapper is configured to transform respective subsets of the permuted sequence of output bits to a respective sequence of BICM transmit symbols.

38. The communications apparatus of claim 37, wherein communications apparatus is further configured to use the sequence of BICM transmit symbols to produce a transmission signal, and the transmission signal is a member of the group consisting of a wireless communication signal and an optical communication signal;

wherein the transmission signal is a member of the group consisting of a phase-shift keyed (PSK) signal, a quadrature amplitude modulated (QAM) signal, and an orthogonal frequency division multiplexed (OFDM) signal, a multidimensional trellis coded modulation signal, and a multidimensional coded modulation signal.

39. The communications apparatus of claim 18, further comprising:

an outer encoder configured to transform a sequence of input bits to the sequence of r×

m input bits, wherein the sequence of N=rm input bits is encoded in accordance with an outer code, and the outer code is a member of the group consisting of a block code, a Low Density Parity Check (LDPC) code, a convolutional code transformed to a block code, and a non-recursive convolutional code; and

a state based modulator configured to transform bits from the permuted sequence of output bits into a sequence of transmit symbols.

40. The communications apparatus of claim 37, wherein the state-based modulator modulates in accordance with a continuous phase modulation (CPM).

41. The communications apparatus of claim 18, further comprising:

a receiver function, configured to receive a received signal and to produce therefrom a vector of bit metrics, wherein the received signal is a received version of a transmitted signal that was concatenated encoded by a concatenated encoder that comprised a plurality of component codes and a second constrained interleaver, wherein the second constrained interleaver implements the permutation function; and

an iterative decoder configured to iteratively decode, using a plurality of component decoding functions, a plurality of deinterleaving functions, and the constrained interleaver, a plurality of respective bit sequences, wherein each respective bit sequence is a respective member of the group consisting of a bit metrics sequence and an extrinsic information sequence, and the plurality of deinterleavers perform deinterleaving operations using an inverse operation of the permutation function.

42. A method for use in a communications apparatus that includes a constrained interleaver operative to rearrange an ordering of a sequence of N=rm input bits in accordance with a permutation function in order to produce a permuted sequence of output bits, wherein N and m are positive integers, m>

1, the method comprising

rearranging the sequence of N=rm input bits in accordance with the permutation function, wherein the permutation function is equivalent to performing the following operations;

applying a word-level pseudo-random permutation function to pseudo-randomly rearrange an ordering of a set of multi-bit words embedded in the sequence of N=rm input bits;

loading the N r=rm number of input bits into a r×

m array of bits, wherein the r×

m array has r rows and m columns, and the bits are serially loaded into the r×

m array of bits along rows,

applying an i^th pseudo-random row permutation function to each row i, for i=1, 2, . . . r, wherein the i^th pseudo-random row permutation function pseudo-randomly rearranges an ordering of m bits in the row, wherein a number of ways that the i^th respective pseudo-random permutation function can pseudo-randomly rearrange the m bits in the i^th row is restricted in accordance with at least one inter-row constraint; and

reading bits out of the r×

m array along r-bit columns to form the permuted sequence of output bits.

43. The method of claim 42, wherein m=ρ

n, where ρ and

n are positive integers, and each multi-bit word corresponds to an n-bit word, whereby there are p number of n-bit words per row.

44. The method of claim 42, wherein each multi-bit word corresponds to a multi-bit codeword associated with a corresponding component code that is a member of the group consisting of a common component code and a selected one of a plurality of component codes.

45. The method of claim 42, wherein the at least one inter-row constraint restricts the i^th respective pseudo-random permutation function in accordance with how coded bits are already placed by a second pseudo-random permutation function corresponding to a second row different from the i^th row.

46. The method of claim 45, wherein the at least one inter-row constraint ensures that coded bits of any codeword on the i^th row can share no more than a pre-defined integer, k(l), number of columns with coded bits of any codeword placed on the (i−

l)^th row, where l=1, 2, . . . l_max, where l is a positive integer representative of a row offset and l_max is a positive integer representative of a maximum row offset to which the inter-row constraint will be applied.

47. The method of claim 46, wherein the inter-row constraint is configured to interpret the integer (i−

l) in a cyclic fashion in accordance with a modulo r integer arithmetic.

48. The method of claim 42, wherein the serially loaded into the r×

m array of bits along rows corresponds to a row-major order.

49. The method of claim 42, wherein the reading bits out of the r×

m array along r-bit columns corresponds to a column-major order.

50. The method of claim 42, wherein the reading bits out of the r×

m array along r-bit columns is performed from top to bottom in each r-bit column during the reading of the bits out of the r×

m array.

51. The method of claim 42, wherein each of the permutation function, the n-bit word-level permutation function and the i^th pseudo-random row permutation function, for i=1, 2, . . . q, corresponds to a respective pseudo randomization that is predetermined prior to a runtime, wherein the runtime corresponds to a time when the method is operative.

52. The method of claim 51, further comprising:

using at least one vector of pointers to facilitate the rearranging.

53. The method of claim 48, wherein using comprises table lookup operations.

54. The method of claim 42, further comprising:

encoding, in accordance with an outer code, a sequence of input bits to generate the sequence of N=rm input bits, wherein the outer code is a member of the group consisting of a block a code, a LDPC (Low Density Parity Check) code, a convolutional code transformed to a block code, and a non-recursive convolutional code;

encoding, in accordance with an inner recursive convolutional code (IRCC), the permuted sequence of output bits to a sequence of inner-encoded bits, whereby the sequence of inner-encoded bits constitutes a serially-concatenated sequence of bits that incorporates coding from both the inner code and the outer code in accordance with a serially-concatenated code that has a minimum Hamming distance of d_sc;

wherein the outer code has a minimum Hamming distance of d_o and the inner code has a minimum Hamming distance of d_i;

wherein the integer r is selected to be large enough to enforce d_sc>

d₀d_i.

55. The method of claim 54, wherein the communications apparatus is a member of the group consisting of a headend system configured to communicate with a plurality of user devices, a user device configured to communicate with the headend system, a peer-to-peer communication device, an optical communications device, an optical communications device configured to support a backbone link, an optical communications device configured to support backbone Internet traffic, a cellular communications headend system, a cellular mobile communications device, and a mobile user data enabled communications device.

56. The method of claim 54, wherein the convolutional code transformed to a block code includes one or more termination bits.

57. The method of claim 56, wherein the one or more termination bits comprises a complete set of termination bits, whereby the convolutional code transformed to a block code is an equivalent block code where the convolutional code is terminated.

58. The method of claim 54, wherein the outer code is a block code and the block code is a non-binary code which is a member of the group consisting of a BCH code and a Reed-Solomon (RS) code.

59. The method of claim 54, further comprising:

mapping the sequence of inner-encoded bits to a transmission signal, wherein the mapping is a member of the group consisting of a stateless signal mapping and a state-based modulation.

60. The method of claim 54, further comprising:

mapping a sequence of encoded bits to a transmission signal, wherein the mapping is a member of the group consisting of a stateless signal mapping and a state-based modulation, wherein the encoded bits include coding from at least both the inner code and the outer code.

61. The method of claim 42, the communication apparatus further comprising:

encoding, in accordance with an outer code, a sequence of input bits to generate the sequence of N=rm input bits, wherein the outer code is a member of the group consisting of a block a code, a LDPC (Low Density Parity Check) code, a convolutional code transformed to a block code, and a non-recursive convolutional code;

mapping the permuted sequence of output bits, wherein the mapping is a Bit-Interleaved Coded Modulation (BICM) mapping that transforms respective subsets of the permuted sequence of output bits to a respective sequence of BICM transmit symbols.

62. The method of claim 61, further comprising,

using the sequence of BICM transmit symbols to produce a transmission signal, wherein the transmission signal is a member of the group consisting of a wireless communication signal and an optical communication signal;

wherein the transmission signal is a member of the group consisting of a phase-shift keyed (PSK) signal, a quadrature amplitude modulated (QAM) signal, and an orthogonal frequency division multiplexed (OFDM) signal, a multidimensional trellis coded modulation signal, and a multidimensional coded modulation signal.

63. The method of claim 42, further comprising:

encoding, in accordance with an outer code, a sequence of input bits to generate the sequence of N=rm input bits, wherein the outer code is a member of the group consisting of a block a code, a LDPC (Low Density Parity Check) code, a convolutional code transformed to a block code, and a non-recursive convolutional code; and

mapping, in accordance with a state based modulation scheme, bits from the permuted sequence of output bits into a sequence of transmit symbols.

64. The method of claim 63, wherein the state-based modulator modulates in accordance with a continuous phase modulation (CPM).

65. The method of claim 42, further comprising:

receiving a received signal and producing therefrom a vector of bit metrics, wherein the received signal is a received version of a transmitted signal that was concatenated encoded by a concatenated encoder that comprised a plurality of component codes and a second constrained interleaver, wherein the second constrained interleaver implements the permutation function; and

iteratively decoding, using a plurality of component decoding functions, a plurality of deinterleaving functions, and the constrained interleaver, a plurality of respective bit sequences, wherein each respective bit sequence is a respective member of the group consisting of a bit metrics sequence and an extrinsic information sequence, and the plurality of deinterleavers perform deinterleaving operations using an inverse operation of the permutation function.