Efficient address generation for convolutional interleaving using a minimal amount of memory

A method of convolutionally deinterleaving a stream of data, the convolutional interleaving being accomplished at a designated interleaving depth (d) and a designated interleaving block length (N), wherein a first symbol in a designated block has a predetermined delay associated therewith and each subsequent symbol in the designated block has a delay equal to (d-1) more than its predecessor symbol, the method comprising the steps of:

• calculating a plurality of delay related arrays each including a number of elements equal to the designated block length, wherein the delay related arrays cooperate with the designated block length to define the delay associated with each symbol in the designated block;
• calculating an initial value array, a lower limit array and an upper limit array based upon the delay related arrays, wherein each symbol in a designated block has an associated interleaving orbit defined by corresponding values in the initial value, lower limit and upper limit arrays;
• and
• generating a convolutional deinterleaving addressing scheme utilizing the initial value, lower limit and upper limit arrays.

A convolutional interleaver arranged to convolutionally interleave an incoming stream of data and output an interleaved stream of bits, the stream of bits being conceptually partitioned into blocks, the interleaver comprising:

• memory arranged to temporarily store received data bits during an interleaving process;
• an address generator arranged to generate a sequence of addresses used to write the incoming stream of data into the memory and to read the interleaved stream of bits from the memory using an upper limit array, a lower limit array and an initial value array, wherein the addresses are generated using the steps of setting the addresses for a first received block of data equal to addresses identified in the initial value array and for each element in each subsequent block of data,
• (a) determining whether an address for a corresponding element in an immediately preceeding block is equal to a corresponding value in the lower limit array;
• (b) setting the address of the element in the subsequent block of data to the corresponding value in the upper limit array when it is determined that the address for the corresponding element in the previous block is equal to the corresponding value of the lower limit array;
• (c) setting the address of the element in the subsequent block of data to a value that is indexed from the address of the corresponding element in the previous block by a designated index amount when it is determined that the address of the corresponding element in the previous block is not equal to the corresponding value in the lower limit array;
• and
• (d) repeating steps (a)-(c) for additional subsequent blocks of data.

A method of convolutionally interleaving a stream of data, the convolutional interleaving being accomplished at a designated interleaving depth (d) and a designated interleaving block length (N), wherein a first symbol in a designated block has a predetermined delay associated therewith and each subsequent symbol in the designated block has a delay equal to (d-1) more than its predecessor symbol, the method comprising the steps of:

• calculating a plurality of delay related arrays each including a number of elements equal to the designated block length, wherein the delay related arrays cooperate with the designated block length to define the delay associated with each symbol in the designated block;
• calculating a plurality of orbit defining arrays that define interleaving orbits, wherein the orbit defining arrays are calculated based at least in part upon the delay related arrays;
• and
• generating a convolutional interleaving addressing scheme utilizing the orbit defining arrays.

A method of convolutionally deinterleaving a stream of data, the convolutional interleaving being accomplished at a designated interleaving depth (d) and a designated interleaving block length (N), wherein a first symbol in a designated block has a predetermined delay associated therewith and each subsequent symbol in the designated block has a delay equal to (d-1) more than its predecessor symbol, the method comprising the steps of:

• calculating a plurality of delay related arrays each including a number of elements equal to the designated block length, wherein the delay related arrays cooperate with the designated block length to define the delay associated with each symbol in a given block,
• calculating a plurality of orbit defining arrays that define interleaving orbits, wherein the orbit defining arrays are calculated based at least in part upon the delay related arrays;
• and
• generating a convolutional deinterleaving addressing scheme utilizing the orbit defining arrays.

A convolutional interleaver arranged to convolutionally interleave an incoming stream of data and output an interleaved stream of bits, the stream of bits being conceptually partitioned into blocks, the interleaver comprising:

• memory arranged to temporarily store received data bits during an interleaving process;
• an address generator arranged to generate a sequence of addresses used to write the incoming stream of data into the memory and to read the interleaved stream of bits from the memory using a plurality of orbit defining arrays, wherein the addresses are generated using the steps of setting the addresses for a first received block of data equal to addresses identified in the orbit defining arrays and for each element in each subsequent block of data,
• (a) determining whether an address for a corresponding element in an immediately preceeding block is equal to a corresponding value defined by the orbit defining arrays;
• (b) setting the address of the element in the subsequent block of data to the corresponding value defined at least in part by a first orbit defining array selected from the orbit defining arrays when it is determined that the address for the corresponding element in the previous block is equal to the corresponding value defined at least in part by a second orbit defining array selected from the orbit defining arrays;
• (c) setting the address of the element in the subsequent block of data to a value that is indexed from the address of the corresponding element in the previous block by a designated index amount when it is determined that the address of the corresponding element in the previous block is not equal to the corresponding value defined at least in part by the second orbit defining array, and
• (d) repeating steps (a)-(c) for additional subsequent blocks of data.