Methods and devices for randomizing burst errors
View Patent ↗Error bursts are randomized by an interleaver which makes use of “set leaders” to generate permutation indices. The permutation indices are used to route bits from initial positions in an input bit stream to re-arranged or randomized positions in an output bit stream. When the output bit stream is then transmitted and subsequently received by a de-interleaver which returns the received bits to their initial, pre-randomized positions, the resulting received signal has an acceptable bit error rate.
1. An interleaver comprising:
a set leader generator operable to generate four set leader values for each set of sixteen initial indices, wherein each index within the initial set of indices is associated with an initial position of a bit in an input bit stream;
an inner set index generator operable to generate sixteen permutated indices for each four set leader values; and
a bit router operable to route each bit in the input bit stream to a randomized position in an output bit stream in accordance with its permutated index.
2. The interleaver as in claim 1 wherein the bit router is further operable to route input bits from an input bit stream to randomized positions in an output bit stream using the permutated indices.
3. The interleaver as in claim 1 wherein the set leader generator and inner set generator each comprises a plurality of flip-flops.
4. The interleaver as in claim 1 wherein the bit router comprises an addressable WRITE and an addressable READ, random-access memory (RAM) section.
5. The interleaver as in claim 1 , wherein the interleaver comprises a wireless local area network (LAN) modem.
6. The interleaver in claim 1 wherein the set leader generator is further operable to generate a group of subsequent set leader values from four preset set leader values of 0, 13, 24 and 37.
7. The interleaver as in claim 6 wherein the set leader generator is further operable to generate the subsequent set leader values by repeatedly incrementing a first set leader value by 1, repeatedly decrementing a second set leader value by one, or incrementing the second value by three, repeatedly incrementing a third set leader value by one and repeatedly decrementing a fourth set leader value by one, or incrementing the fourth value by three.
8. The interleaver as in claim 1 , wherein the set leader values generated by the set leader generator are given by:
Index
Set
Leader 1
Leader 2
Leader 3
Leader 4
1
0
13
24
37
2
1
12
25
36
3
2
15
26
39
4
3
14
27
38
5
4
17
28
41
6
5
16
29
40
7
6
19
30
43
8
7
18
31
42
9
8
21
32
45
10
9
20
33
44
11
10
23
34
47
12
11
22
35
46.
9. A permutation-based de-interleaver operable to route randomly positioned bits in a received bit stream to initial positions in an output bit stream based on permutated indices,
wherein each randomly positioned bit in the received bit stream was positioned based on one of sixteen permutated indices generated from four set leader values for each set of sixteen initial indices associated with an initial position of a bit in an original input bit stream.
10. A permutation-based interleaver comprising:
means for generating four set leader values for each set of sixteen initial indices, wherein each index within the initial set of indices is associated with an initial position of a bit in an input bit stream;
means for generating sixteen permutated indices for each four set leader values; and
means for routing each bit in the input bit stream to a randomized position in an output bit stream in accordance with its permutated index.
11. The interleaver as in claim 10 further comprising means or routing input bits from an input bit stream to randomized positions in an output bit stream using the permutated indices.
12. The interleaver as in claim 11 wherein the means for routing comprises an addressable WRITE and an addressable READ, random-access memory (RAM) section.
13. The interleaver as in claim 10 , wherein the interleaver comprises a wireless local area network (LAN) modem.
14. The interleaver as in claim 10 further comprises means for generating a group of subsequent set leader values from four preset set leader values of 0, 13, 24 and 37.
15. The interleaver as in claim 14 wherein the means for generating the subsequent set leader values further comprises means for generating said values by repeatedly incrementing a first set leader value by 1, repeatedly decrementing a second set leader value by one, or incrementing the second value by three, repeatedly incrementing a third set leader value by one and repeatedly decrementing a fourth set leader value by one, or incrementing the fourth value by three.
16. The interleaver as in claim 10 , wherein the values generated by the means for generating set leader values are given by:
Index
Set
Leader 1
Leader 2
Leader 3
Leader 4
1
0
13
24
37
2
1
12
25
36
3
2
15
26
39
4
3
14
27
38
5
4
17
28
41
6
5
16
29
40
7
6
19
30
43
8
7
18
31
42
9
8
21
32
45
10
9
20
33
44
11
10
23
34
47
12
11
22
35
46.