Convolutional interleaver and method for generating memory address therefor

• US 6,035,427 A
• Filed: 07/01/1997
• Issued: 03/07/2000
• Est. Priority Date: 07/01/1996
• Status: Expired due to Term

• Current Assignee: Wi-LAN Inc.
• Original Assignee: Daewoo Electronics Company Limited (Dayou Holdings Co.,Ltd.)
• Inventors: Kweon, Oh Sang
• Primary Examiner(s): Chan, Eddie P.
• Assistant Examiner(s): MCLEAN MAYO, KIMBERLY N
• Application Number:
  US08/886,514
• Time in Patent Office: 980 Days
• Field of Search: 711/202, 711/200, 371/2.1, 371/10.2, 371/22.33, 371/22.35, 371/27.2, 371/37.5, 371/38.1, 371/39.1, 371/44, 714/701, 714/702, 714/728
• US Class Current: 714/702
• CPC Class Codes: H03M 13/2732 Convolutional interleaver; Interleavers using shift-registers or delay lines like, e.g. Ramsey type interleaver
• CPC Class Codes: H03M 13/2764 Circuits therefore

Abstract

A convolutional interleaver for interleaving a data stream composed of N number of data with predetermined interleaving level B to randomize the data stream for an error correction, comprising: an input buffer; a memory; an address generating unit; an output buffer; and a controller, and a method for generating an address of the memory are disclosed. In the method for generating an address of the memory, a basic memory of which the number of vertical end is B-1 and horizontal length is (B-1)×M cell is transformed to an intermediate memory of which the number of vertical end is B-1 and horizontal length is (B/2)×M cell, and a physical address for accessing the intermediate memory is generated. The physical address is maintained during one clock period, while the memory reads the previous data stored in the memory position corresponding to the physical address during the first half period of the clock and stores the current input data in the same memory position corresponding to the physical address during the latter half period of the clock.

Claims

1. A convolutional interleaver for interleaving a data stream composed of N number of consecutive data with an interleaving level B to randomize the data stream for error correction, comprising:

input means for inputting the data stream and outputting a first data of the interleaving level during a first clock and a second to a Bth data of the interleaving level during one half period of a second to a Bth clock, respectively;

storage means having a structure of an intermediate memory having B-1 number of vertical ends with a horizontal cell length of (B/2)×

M modified from a structure of a basic memory having B-1 number of vertical ends with a horizontal cell length of (B-1)×

M by moving some of used storage locations into all of unused storage locations in the basic memory, where M=N/B, said storage means for performing a read operation during one half period of a clock for which a physical address is maintained, and for performing a write operation during the other half period of said clock for which a physical address is maintained;

address generating means for generating the physical address to access said intermediate memory;

output means for outputting the data from said input means during the first clock and the data from said storage means during each of a second to a Bth clock, respectively; and

a controller for receiving a basic vertical address from said address generating means and generating a plurality of control signals for controlling said input means, said output means, and said storage means.

2. The convolutional interleaver according to claim 1, wherein said address generating means comprises;

a basic address generator for generating a basic vertical address, a basic horizontal group address and a horizontal cell address to access said basic memory;

an intermediate address converter for converting said basic vertical address and said basic horizontal group address to an intermediate vertical address and an intermediate horizontal group address to access said intermediate memory; and

a physical address mapper for generating the physical address by using the intermediate vertical address, the intermediate horizontal group address, and the horizontal cell address.

3. The convolutional interleaver according to claim 2, wherein said basic address generator comprises;

a first counter for repeatedly counting from an initial value `-1` to `B-2` by increments of 1 in synchronization with a byte clock and outputting the counted value as the basic vertical address;

a second counter for being initiated by a first carry signal from said first counter, repeatedly counting from an initial value `0` to `M-1` by increments of 1 and outputting the counted value as the horizontal cell address;

a third counter for being initiated by a second carry signal from said second counter, repeatedly counting from an initial value `0` to a `LCM`, where `LCM` is the lowest common multiply for the the integral number to 1˜

(B-1), and outputting the counted value as a recursive period to generate the basic memory address;

an accumulator for adding 1 to said basic vertical address; and

a modulo operator for modulo-operating the counted value from said third counter with the output value of said accumulator and outputting the obtained value as the basic horizontal group address.

4. The convolutional interleaver according to claim 1, wherein said physical address is maintained during one clock, a previous data is read from a position corresponding to the physical address in said storage means during one half period of each clock and a current data from said input means is stored in the same position corresponding to the physical address in said storage means during the other half period of each clock.

5. A method for generating a memory address to interleave a data stream composed of N number of consecutive data with an interleaving level B, comprising the steps of;

(a) disabling a memory access in a first clock of the interleaving level for a first data of B period;

(b) generating a basic vertical address for selecting one of (B-1) number of vertical ends in a basic memory having B-1 number of vertical ends with a horizontal length cell of (B-1)×

M to delay the remaining data except the first data of B period, a basic horizontal group address for selecting one of (B-1) number of horizontal groups in the basic memory, and a horizontal cell address for selecting one of M number of cells in one of the horizontal groups in the basic memory, where M=N/B;

(c) converting the basic vertical address in said (b) step to an intermediate vertical address for selecting one of (B-1) number of vertical ends of an intermediate memory having B-1 number of vertical ends with a horizontal length cell of (B/2)×

M, and the basic horizontal group address in said (b) step to an intermediate horizontal group address for selecting one of (B/2) number of the horizontal groups of said intermediate memory;

(d) generating a physical address for accessing said intermediate memory by using the intermediate vertical address and intermediate horizontal group address in said (c) step, and the horizontal cell address in said (b) step; and

(e) maintaining said physical address in said (d) step during one clock while reading the data during one half period of the clock and writing the data during the other half period of the clock.

6. The method for generating a memory address according to claim 5, wherein in said step (b), the basic vertical address is generated by repeatedly counting from an initial value `-1`to `B-2`, the horizontal cell address is generated by repeatedly counting from an initial value `0` to `M-1`, and the basic horizontal group address is generated by modulo-operating the counted value obtained by repeatedly counting from an initial value `0` to LCM, where LCM is the lowest common multiply for the integral number to 1˜

(B-1), with the value obtained by adding 1 to the basic vertical address.

7. The method for generating a memory address according to claim 5, wherein in said (c) step, the intermediate vertical address is IAV=AV when the basic horizontal group address is 0≦

MAH<

B/2, while converted to IAV=(B-2)-AV when B/2≦

MAH, the intermediate horizontal group address is IMAH=MAH when the basic horizontal group address is 0≦

MAH<

B/2, while converted to IMAH=(B-1)-MAH when B/2≦

MAH.

8. The method for generating a memory address according to claim 5, wherein in said (d) step, the physical address PA=(IMAH×

M+LAH)×

(B-1)+IAV when the intermediate memory is scanned in vertical direction, while transformed to PA=(IAV×

B/2×

M+IMAH)×

M+LAH when the intermediate memory is scanned in horizontal direction.