High spread highly randomized generatable interleavers

A forward error correction encoder for encoding a frame of information bits of size n*m comprising:

• first encoder for encoding said information bits in natural order and for generating first final state information;
• seed ROM for storing a set of n seed values, wherein each seed from said set of seeds has a unique modulo-n value, said set of n seed values having a spread value S greater than 1, and each seed value is a member of a substantially evenly distributed subset of addresses;
• interleaver for generating an interleaved frame of said information bits using said set of seed values;
• second encoder for encoding said interleaved frame, and for generating second final state information.

A forward error correction encoder for encoding a frame of information bits of size n*m=N comprising:

• first encoder for encoding said information bits in natural order and for generating first final state information;
• seed ROM for storing a set of n seed values wherein each seed value is a member of a substantially evenly distributed subset of addresses formed by multiplying a corresponding unique integer value by seed_step, and wherein seed_step is relatively prime to n and m;
• interleaver circuit for generating interleaved addresses by repeatedly modulo-N adding set_step to said set of n seed values, where set_step is relative prime to n and m;
• second encoder for encoding said interleaved frame, and for generating second final state information.

An iterative decoder for decoding a frame of transmitted receive samples for a frame of information bits of size n*m=N comprising:

• seed ROM adapted to store a set of n seed values wherein each seed value is a member of a substantially evenly distributed subset of addresses;
• interleaver circuitry adapted to generate interleaved addresses by selecting a next address for each seed from a corresponding substantially evenly distributed subset of addresses, and for deinterleaving a portion of said receive samples;
• and
• decoder apparatus adapted to generate extrinsic information by decoding said receive samples in a natural order during a first subiteration, and in an interleaved order during a second subiteration.

A forward error correction decoding system comprising:

• sample memory for storing a frame of information samples;
• soft-in-soft-out (SISO) decoder for generating extrinsic information in response to likelihood information and extrinsic information, and for generating state initialization information;
• seed ROM circuit for storing a set of seed addresses, where each seed address is a member of a subset of addresses;
• interleaver address generation circuit for generating interleaved addresses based on seed values contained in said seed ROM, wherein said interleaved addresses are used for interleaving and deinterleaving said extrinsic information, wherein said soft-in-soft-out decoder is initialized by decoding the end of said frame of information samples before beginning to decode the start of said information samples.

A forward error correction encoder for encoding a frame of information bits comprising:

• first encoder for encoding said information bits in natural order and for generating first final state information;
• seed ROM for storing a set of n seed values, wherein said set of n seed values have a spread value S greater than 1, and each seed value is a member of a substantially evenly distributed subset of addresses;
• interleaver for generating an interleaved frame of said information bits using said set of seed values;
• second encoder for encoding said interleaved frame, and for generating second final state information;
• first initialization state calculation circuit for calculating a first init state based on said first final state information;
• and
• second initialization state calculation circuit for calculating a second init state based on said second final state information.

A method of encoding a frame of information bits, comprising:

• encoding said information bits in natural order, and generating first final state information based at least partly thereon;
• providing a set of n seed values, wherein each seed from said set of seeds has a unique modulo-n value, said set of n seed values having a spread value S greater than 1, each of said seed values being a member of a substantially evenly distributed subset of addresses;
• generating an interleaved frame of said information bits using at least said set of seed values;
• encoding said interleaved frame and generating second final state information;
• calculating a first init state based at least in part on said first final state information;
• and
• calculating a second init state based at least in part on said second final state information.

A forward error correction encoder for encoding information bits, comprising:

• first encoder apparatus adapted to encode said information bits in natural order and to generating first final state information;
• seed ROM adapted to store a set of n seed values, wherein each seed from said set of seeds has a unique modulo-n value, said set of n seed values having a spread value S greater than 1, and each seed value being a member of a substantially evenly distributed subset of addresses;
• an interleaver adapted to generate an interleaved frame of said information bits using said set of seed values;
• second encoder apparatus adapted to encode said interleaved frame, and to generate second final state information;
• first state calculation circuitry adapted to calculate a first init state based on said first final state information;
• and
• second state calculation circuitry adapted to calculate a second init state based on said second final state information.

Communications encoder apparatus, comprising:

• first encoder apparatus adapted to encode a plurality of information bits in natural order, and to generate first state information;
• storage apparatus storing a set of n seed values, wherein each seed from said set of seeds has a unique modulo-n value, said set of n seed values having a spread value S greater than a predetermined value, each seed value being a member of a substantially evenly distributed subset of addresses;
• an interleaver adapted to generate an interleaved frame of said information bits using said set of seed values;
• and
• second encoder apparatus adapted to encode said interleaved frame, and for generating second state information.

A forward error correction encoder for encoding a frame of information bits of size n*m=N comprising:

• first encoder apparatus adapted to encode said information bits in natural order and
• generate first final state information;
• a storage device containing a set of n seed values wherein each seed value is a member of a substantially evenly distributed subset of addresses formed by multiplying a corresponding unique integer value by seed_step , said seed_step being relatively prime to n and m;
• interleaver circuitry adapted to produce interleaved addresses by repeatedly modulo-N adding set13 step to said set of n seed values, where set_step is relatively prime to n and m;
• and
• second encoder apparatus adapted to encode said interleaved frame and generate second final state information.

A forward error correction encoder, comprising:

• first means for encoding a plurality of information bits in natural order, and for generating first state information;
• storage means having a set of n seed values, wherein each seed from said set of seeds has a unique modulo-n value, said set of n seed values having a spread value S greater than a predetermined value, each seed value being a member of a substantially evenly distributed subset of addresses;
• interleaver means for producing an interleaved collection of said information bits using said set of seed values;
• and
• second means for encoding said interleaved collection, and for generating second state information.

A communications encoder having an interleaver adapted to interleave a set of n*L Locations according to the method comprising:

• providing a set of first values having a minimum distance between any two first values of L, each of said first values having a different modulo-n index;
• generating a first set of second values, each of said second values of said first set being equal to a corresponding first value plus n modulo-n*L;
• and
• generating additional sets of second values, each second value of said additional sets being equal to a member value from another corresponding set of second values plus n modulo-n*L.

A communications encoder having an interleaver adapted to interleave a set of n*L Locations according to the method comprising:

• providing a set of first values having a minimum distance between any two first values of L, each of said first values having a different modulo-n index;
• generating a first set of second values, each of said second values of said first set being equal to a corresponding first value plus n modulo-n*L;
• and
• generating additional sets of second values, each second value of said additional sets being equal to a member value from another corresponding set of second values plus n modulo-n*L.