Method of interleaving a binary sequence

• US 7,069,492 B2
• Filed: 03/13/2003
• Issued: 06/27/2006
• Est. Priority Date: 03/13/2002
• Status: Expired due to Fees

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Piret, Philippe
• Primary Examiner(s): Lamarre, Guy J.
• Application Number:
  US10/386,722
• Publication Number:
  US 20030177430A1
• Time in Patent Office: 1,202 Days
• Field of Search: 714786-788, 714/701, 714/755, 714/761, 714/762
• US Class Current: 714/762
• CPC Class Codes: H03M 13/2771 Internal interleaver for turbo codes H03M13/2714 and H03M13/2725 take precedence
• CPC Class Codes: H03M 13/2993 Implementing the return to a predetermined state, i.e. trellis termination

Abstract

To interleave a binary sequence a represented by the polynomial

$a\left(x\right)=\sum _{i=0}^{n-1}{a}_i{x}^i,$
where n=R.M with R≧M, i being an integer which may be written i=r.M+c, r and c being integers, r≧0 and c ε [0, M−1], there is obtained, from the sequence a, an interleaved binary sequence a*. The interleaved binary data sequence a* represented by the polynomial

$a^{*}\left(x\right)=\sum _{i=0}^{n-1}{a}_i{x}^{i^{*}}$
where i*=[r−h(c)].M+c mod n, the h(c) being obtained by the choice of an M-tuple h₀=[h₀(0), . . . , h₀(M−1)] of non-negative integers less than R−1 such that, given a predetermined set Π of circulating matrices P of dimension M×M, for any matrix P of Π, the residues modulo R of the components of the vector h₀.P are not nil; and the corresponding choice of an M-tuple h obtained from h₀ by the application of a permutation moving h₀(c) to position L×c mod M, the integer L being relatively prime with M. (It is noted that the above underlining of the variables, and the above single bracketing, is in the original and is meant to be permanent.)

Claims

1. A method of interleaving a binary data sequence a represented by a polynomial

$a$

( x ) = ∑

i = 0 n - 1 ⁢

a i ⁢

x i ,

n being a product of two integers R and M such that R≧

M, i being an integer which may be written i=r.M+c, r being a non-negative integer and c being an integer in the interval [0, M−

1], said method comprising obtaining, from the sequence a, an interleaved binary data sequence a* represented by a polynomial

$a^{*}<br><br>\left(x\right)=\underset{i=0}{\overset{n-1}{\sum <br><br>}}<br><br>a_i<br><br>x^{i^{*}}$

where i*=[r−

h(c)].M+c mod n, the numbers h(c) being obtained by;

the choice of an M-tuple h₀=[h₀(0), . . . , h₀(M−

1)] of non-negative integers less than R−

1 such that, given a predetermined set Π

of circulating matrices P of dimensions M×

M, for any matrix P of Π

, the residues modulo R of the components of the vector h₀.P are not nil; and

the corresponding choice of an M-tuple h=[h(0), . . . , h(M−

1)] obtained from the M-tuple h₀ by the application of a permutation moving the element h₀(c) to position L×

c mod M, L being an integer relatively prime with M.

2. A method according to claim 1, wherein the set Π

contains circulating matrices P₁ and P₂ such that;

the first column of P₁ is [1-2 1 0 . . . 0]^T and

the first column of P₂ is [2-2 0 0 . . . 0]^T,

where ^T designates the transposition.

3. A method according to claim 1, wherein the set Π

contains circulating matrices P₃ to P₈ such that;

the first column of P₃ is [1-1-1 1 0 . . . 0]^T,

the first column of P₄ is [1-1 1-1 0 . . . 0]^T,

the first column of P₅ is [1 0-2 1 0 . . . 0]^T,

the first column of P₆ is [1-2 0 1 0 . . . 0]^T,

the first column of P₇ is [2-1-1 0 0 . . . 0]^T and

the first column of P₈ is [1 1-2 0 0 . . . 0]^T,

where ^T designates the transposition.

4. A method according to claim 1, wherein the set Π

contains circulating matrices P₉ to P₂₀ such that;

the first column of P₉ is [1 1-1-1 0 . . . 0]^T,

the first column of P₁₀ is [1-1 0 1-1 0 . . . 0]^T,

the first column of P₁₁ is [1-1 0-1 1 0 . . . 0]^T,

the first column of P₁₂ is [1 0-1-1 1 0 . . . 0]^T,

the first column of P₁₃ is [1-1-1 0 1 0 . . . 0]^T,

the first column of P₁₄ is [1 0-1 1-1 0 . . . 0]^T,

the first column of P₁₅ is [1-1 1 0-1 0 . . . 0]^T,

the first column of P₁₆ is [1 0-2 0 1 0 . . . 0]^T,

the first column of P₁₇ is [1 0 0-2 1 0 . . . 0]^T,

the first column of P₁₈ is [1-2 0 0 1 0 . . . 0]^T,

the first column of P₁₉ is [1 0 1-2 0 0 . . . 0]^T and

the first column of P₂₀ is [2-1 0-1 0 0 . . . 0]^T,

where ^T designates the transposition.

5. A method according to claim 1, wherein the set Π

contains circulating matrices P₂₁ to P₂₄ such that;

the first column of P₂₁ is [1-3 2 0 0 . . . 0]^T,

the first column of P₂₂ is [2-3 1 0 0 . . . 0]^T,

the first column of P₂₃ is [1-2 2-1 0 . . . 0]^T and

the first column of P₂₄ is [3-3 0 0 0 . . . 0]^T,

where ^T designates the transposition.

6. A method according to claim 1, wherein the set Π

contains circulating matrices P₁ to P₈ such that;

the first column of P₁ is [1-2 1 0 . . . 0]^T,

the first column of P₂ is [2-2 0 0 . . . 0]^T,

the first column of P₃ is [1-1-1 1 0 . . . ₀]^T,

the first column of P₄ is [1-1-1 0 . . . 0]^T,

the first column of P₅ is [1 0-2 1 0 . . . 0]^T,

the first column of P₆ is [1-2 0 1 0 . . . 0]^T,

the first column of P₇ is [2-1-1 0 0 . . . 0]^T and

the first column of P₈ is [1 1-2 0 0 . . . 0]^T,

where ^T designates the transposition.

7. A method according to claim 1, wherein the set Π

contains circulating matrices P₁ to P₂₀ such that;

the first column of P₁ is [1-2 1 0 . . . 0]^T,

the first column of P₂ is [2-2 0 0 . . . 0]^T,

the first column of P₃ is [1-1-1 1 0 . . . 0]^T,

the first column of P₄ is [1-1 1-1 0 . . . 0]T,

the first column of P₅ is [1 0-2 1 0 . . . 0]T,

the first column of P₆ is [1-2 0 1 0 . . . 0]T,

the first column of P₇ is [2-1-1 0 0 . . . 0]^T,

the first column of P₈ is [1 1-2 0 0 . . . 0]^T,

the first column of P₉ is [1 1-1-1 0 . . . 0]^T,

the first column of P₁₀ is [1-1 0 1-1 0 . . . 0]^T,

the first column of P₁₁ is [1-1 0-1 1 0 . . . 0]^T,

the first column of P₁₂ is [1 0-1-1 1 0 . . . 0]^T,

the first column of P₁₃ is [1-1-1 0 1 0 . . . 0]^T,

the first column of P₁₄ is [1 0-1 1-1 0 . . . _0]^T,

the first column of P₁₅ is [1-1 1 0-1 0 . . . _0]^T,

the first column of P₁₆ is [1 0-2 0 1 0 . . . 0]^T,

the first column of P₁₇ is [1 0 0-2 1 0 . . . 0]^T,

the first column of P₁₈ is [1-2 0 0 1 0 . . . 0]^T,

the first column of P₁₉ is [1 0 1-2 0 0 . . . 0]^T and

the first column of P₂₀ is [2-1 0-1 0 0 . . . 0]^T,

where ^T designates the transposition.

8. A method according to claim 1, wherein the set Π

contains circulating matrices P₁ to P₂₄ such that;

the first column of P₁ is [1-2 1 0 . . . 0]^T,

the first column of P₂ is [2-2 0 0 . . . 0]^T,

the first column of P₃ is [1-1-1 1 0 . . . 0]^T,

the first column of P₄ is [1-1 1-1 0 . . . 0]^T,

the first column of P₅ is [1 0-2 1 0 . . . 0]^T,

the first column of P₆ is [1-2 0 1 0 . . . 0]^T,

the first column of P₇ is [2-1-1 0 0 . . . 0]^T,

the first column of P₈ is [1 1-2 0 0 . . . 0]^T,

the first column of P₉ is [1 1-1-1 0 . . . 0]^T,

the first column of P₁₀ is [1-1 0 1-1 0 . . . 0]^T,

the first column of P₁₁ is [1-1 0-1 1 0 . . . 0]^T,

the first column of P₁₂ is [1 0-1-1 1 0 . . . 0]^T,

the first column of P₁₃ is [1-1-1 0 1 0 . . . 0]^T,

the first column of P₁₄ is [1 0-1-1 0 . . . 0]T,

the first column of P₁₅ is [1-1 1 0-1 0 . . . 0]^T,

the first column of P₁₆ is [1 0-2 0 1 0 . . . 0]^T,

the first column of P₁₇ is [1 0 0-2 1 0 . . . 0]^T,

the first column of P₁₈ is [1-2 0 0 1 0 . . . ]^T,

the first column of P₁₉ is [1 0 1-2 0 0 . . . 0]^T,

the first column of P₂₀ is [2-1 0-1 0 0 . . . 0]^T,

the first column of P₂₁ is [1-3 2 0 0 . . . 0]^T,

the first column of P₂₂ is [2-3 1 0 0 . . . 0]^T,

the first column of P₂₃ is [1-2 2-1 0 . . . 0]^T and

the first column of P₂₄is [3-3 0 0 0 . . . 0]^T,

where ^T designates the transposition.

9. A method according to claim 1, wherein the set Π

contains circulating matrices P₁, P₂ and P₂₁ to P₂₄ such that;

the first column of P₁ is [1-2 1 0 . . . 0]^T,

the first column of P₂ is [2-2 0 0 . . . 0]^T,

the first column of P₂₁ is [1-3 2 0 0 . . . 0]^T,

the first column of P₂₂ is [2-3 1 0 0 . . . 0]^T,

the first column of P₂₃ is [1-2 2-1 0 . . . 0]^Tand

the first column of P₂₄ is [3-3 0 0 0 . . . 0]^T,

where ^T designates the transposition.

10. A method according to claim 1, wherein the set Π

contains circulating matrices P₁ to P₈ and P₂₁ to P₂₄ such that;

the first column of P₁ is [1-2 1 0 . . . 0]^T,

the first column of P₂ is [2-2 0 0 . . . 0]^T,

the first column of P₃ is [1-1-1 1 0 . . . 0]^T,

the first column of P₄ is [1-1 1-1 0 . . . 0]^T,

the first column of P₅ is [1 0-2 1 0 . . . 0]^T,

the first column of P₆ is [1-2 0 1 0 . . . 0]^T,

the first column of P₇ is [2-1-1 0 0 . . . 0]^T,

the first column of P₈ is [1 1-2 0 0 . . . 0]^T,

the first column of P₂₁ is [1-3 2 0 0 . . . 0]^T,

the first column of P₂₂ is [2-3 1 0 0 . . . 0]^T,

the first column of P₂₃ is [1-2 2-1 0 . . . 0]^Tand

the first column of P₂₄ is [3-3 0 0 0 . . . 0]^T,

where ^T designates the transposition.

11. A method of encoding for the transmission of information, implementing an interleaving method according to claim 1, and wherein:

an integer L is the period which is common to predetermined first and second polynomials with binary coefficients g(x) and g*(x) and of degree d and of constant term equal to 1;

the information is presented in the form of binary sequences u of length l=n−

2d, where n is a predetermined multiple of L; and

for each of the sequences u, a triplet v is produced of binary sequences a,b,c intended to be transmitted and obtained as follows;

the sequence b is represented by the polynomial b(x)=a(x).f₁(x)/g(x), where f₁(x) is a second predetermined polynomial with binary coefficients, not having a common divisor with g(x),

the sequence c is represented by the polynomial c(x)=a*(x).f₂(x)/g*(x), where f₂(x) is a third predetermined polynomial with binary coefficients, not having a common divisor with g*(x), and where a*(x) is a polynomial associated with a sequence a* produced by interleaving of the sequence a, and

the sequence a is of length n and is obtained by inserting 2d padding bits in the sequence u in order that the polynomial

$a<br><br>\left(x\right)=\underset{i=0}{\overset{n-1}{\sum <br><br>}}<br><br>a_i<br><br>x^i$

 

associated with a be divisible by g(x) and that the polynomial a*(x) be divisible by g*(x).

12. An encoding method according to claim 11, wherein the first and second polynomials g(x) and g*(x) are identical.

13. A decoding method, including the decoding of received sequences which were transmitted after having been encoded by an encoding method according to claim 11.

14. A device for encoding sequences of data intended to be transmitted, the sequences being encoded by an encoding method according to claim 11, said device comprising:

means for obtaining, for each sequence of data u, said sequence a associated with u by inserting said 2d padding bits in the sequence u, and

at least one encoder comprising an interleaver capable of performing the permutation provided for in said interleaving method.

15. A decoding device intended to implement a decoding method according to claim 13, comprising:

at least one decoder comprising two interleavers capable of performing the permutation provided for in said interleaving method, and a deinterleaver adapted to reverse that permutation, and

means for producing a binary sequence û

by removing 2d bits from an estimated sequence â

obtained at the issue of the decoding of sequences a′

, b′ and

c′

received corresponding respectively to the transmitted sequences a, b and c, the 2d bits to be removed corresponding to the 2d bits inserted in the sequence u to obtain the sequence a.

16. Apparatus for transmitting encoded digital signals, comprising an encoding device according to claim 14 and having means for transmitting the encoded sequences a, b, and c.

17. Apparatus for receiving encoded digital signals, comprising a decoding device according to claim 15 and comprising means for receiving the sequences a′

, b′

, and c′

.

18. Telecommunications network, comprising at least one transmission apparatus according to claim 16.

19. Telecommunications network, comprising at least one reception apparatus according to claim 17.

20. A base station in a telecommunications network, comprising at least one transmission apparatus according to claim 16.

21. A base station in a telecommunications network, comprising at least one reception apparatus according to claim 17.

22. A mobile station in a telecommunications network, comprising at least one transmission apparatus according to claim 16.

23. A mobile station in a telecommunications network, comprising at least one reception apparatus according to claim 17.

24. An information storage medium, which can be read by a computer or a microprocessor storing instructions of a computer program, making it possible to implement an interleaving method according to claim 1.

25. An information storage medium, which can be read by a computer or a microprocessor storing instructions of a computer program, making it possible to implement an encoding method according to claim 11.

26. An information storage medium, which can be read by a computer or a microprocessor storing instructions of a computer program, making it possible to implement a decoding method according to claim 13.

27. A partially or entirely removable information storage medium, which can be read by a computer or a microprocessor storing instructions of a computer program, making it possible to implement an interleaving method according to claim 1.

28. A partially or entirely removable information storage medium, which can be read by a computer or a microprocessor storing instructions of a computer program, making it possible to implement an encoding method according to claim 11.

29. A partially or entirely removable information storage medium, which can be read by a computer or a microprocessor storing instructions of a computer program, making it possible to implement a decoding method according to claim 13.

30. A computer program product stored in a computer-readable storage medium, and comprising sequences of instructions to implement an interleaving method according to claim 1.

31. A computer program product stored in a computer-readable storage medium, and comprising sequences of instructions to implement an encoding method according to claim 11.

32. A computer program product stored in a computer-readable storage medium, and comprising sequences of instructions to implement a decoding method according to claim 13.