# US 2006/0156170 A1 · Methods for the generation of S-random interleavers for turbo decoders with a parallel structure

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2006/0156170 A1
- Document ID: US20060156170A1
- Status: Published application
- Kind: A1
- Application number: 11/290,455
- Filed: 2005-12-01
- Published: 2006-07-13
- Earliest claimed: 2004-12-01
- Assignees: Istituto Superiore Mario Boella Per Le Tecnologie Dell' Informazione E Delle Telecomunicazioni
- Inventors: Libero Dinoi; Sergio Benedetto
- Web page: https://patentgrep.com/patent/US20060156170A1

## CPC

- H03M 13/2796: {Two or more interleaving operations are performed jointly, e.g. the first and second interleaving operations defined for 3GPP UMTS are performed jointly in a single interleaving operation}
- H03M 13/2746: {S-random interleaver}
- H03M 13/2789: {Interleaver providing variable interleaving, e.g. variable block sizes}
- H03M 13/2792: {Interleaver wherein interleaving is performed jointly with another technique such as puncturing, multiplexing or routing}
- H03M 13/6561: {Parallelized implementations}
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)

## Abstract

The method allows to obtain, starting from an initial S-random interleaver permutation, stored in memory devices and having a spread S, a size K and a degree of parallelism M<K, and collision-free, an interleaver permutation having an increased size, which is also collision-free, by an expansion technique which is carried out by electronic processing devices connected to the memory devices. In each of the subsequent iteration, the initial interleaver permutation is added with M terms or elements which obey a predetermined condition, inserted in respective positions which satisfy a predetermined relationship. In each of said iterations, the choice of the values the M elements added to the permutation is made by means of a procedure which implements a predetermined optimisation criterion, adapted to maximise the spread value of the resulting interleaver permutation.

## Claims

### Claim 1

An incremental method for obtaining, starting from an initial S-random interleaver permutation Π, stored in memory means and having a spread S, a size K and a degree of parallelism M<K, and collision-free, an interleaver permutation with an increased size, which is also collision-free, through an expansion technique which is carried out by means of electronic processing means connected to said memory means;
wherein in each of successive iterations, the initial interleaver permutation is added with M terms or elements which satisfy the following relationship:
∀
i
∈
[
0
;
K
M
-
1
]
,
∀
j
,
k
∈
[
0
;
M
-
1
]
,
⁢
with
⁢
⁢
j
≠
k
⁢
:
⁢
⁢
⌊
Π
⁡
(
i
+
K
M
⁢
j
)
/
(
K
/
M
)
⌋
≠
⌊
Π
⁡
(
i
+
K
M
⁢
k
)
/
(
K
/
M
)
⌋
wherein i, j, k are indices which indicate the position of the terms or elements in the interleaver permutation, said M terms or elements being added in respective positions iz such that:
i
z
+
1
=
(
i
z
+
K
M
)
mod
⁢
⁢
K
,
z
=
0
,
…
⁢
,
K
-
1

### Claim 2 (depends on 1)

A method according to claim 1, wherein in each of said iterations the choice of the values of the M elements added to the permutation is made by a procedure which implements a predetermined optimisation criterion, adapted to maximise the value of the spread of the resulting interleaver permutation.

### Claim 3 (depends on 2)

A method according to claim 2, wherein at each iteration one identifies which positions (i, j) and terms (Π(i), Π(j)) of the initial permutation correspond to violations which prevent the obtention of a spread value incremented by 1, and a new element is inserted into the permutation, in a position belonging to the interval [min(i,j)+1; max(i,j)], or a new element or term with a value belonging to the interval [min((Π(i), Π(j))+1; max(Π(i), Π(j))] and this as long as such an insertion does not introduce any new spread violations.

### Claim 4 (depends on 1)

A method according to claim 1, wherein, particularly for interleaver permutations having a high degree M of parallelism, particularly greater than 5, the interleaver permutation with an increased size is obtained by-combining a temporal permutation Πt and a spatial permutation Πs.

### Claim 5 (depends on 4)

A method according to claim 4, wherein for obtaining an interleaver permutation having a degree of parallelism M=MbR, wherein R is an integer, a collision-free S-random interleaver permutation is used, having a degree of parallelism equal to Mb and satisfying the relationship
min
⁢
(

Π
⁢
(
i
)
-
Π
⁢
(
j
)

,
K
M
-

Π
⁢
(
i
)
-
Π
⁢
(
j
)

)
+
min
⁢
(

i
-
j

,
K
M
-

i
-
j

)
>
S
tr
.

### Claim 6 (depends on 5)

A method according to claim 5, wherein as the spatial permutation Πs one uses a permutation obeying the relationship
∀
i
∈
[
0
;
K
R
-
1
]
,
⁢
∀
j
∈
[
0
;
R
-
1
]
⁢
:
⁢
⁢
Π
⁡
(
i
+
K
R
⁢
j
)
=
Π
b
⁡
(
i
)
+
K
R
⁡
[
Π
S
⁡
(
Π
b
⁡
(
i
)
mod
⁢
⁢
P
)
+
j
]
mod
⁢
⁢
R
wherein P is the period of the spatial permutation Πs.

### Claim 7 (depends on 1, 4)

A method for obtaining, collision-free S-random interleaver permutation having a predetermined degree of parallelism and a length comprised between a minimum value N1 and a maximum value N2, the method comprising the steps of:
storing in memory devices a collision-free S-random interleaver permutation having the predetermined degree of parallelism and a length having a predetermined value Nthr comprised between N1 and N2, said permutation being obtained by an incremental method according to claim 1;
generating interleaver permutations having a length comprised between N1 and Nthr, by a pruning method applied to the said permutation which is stored in said memory devices; and
generating interleaver permutations having a length comprised between Nthr and N2 by an incremental method according to claim 4.
