In-place transformations with applications to encoding and decoding various classes of codes

In an decoder that decodes data arranged as a plurality of encoded source symbols into an plurality of decoded symbols, a method of performing a transformation from the encoded symbols to the decoded symbols, wherein some number, r, of the encoded symbols are to be transformed into d decoded symbols, the method comprising:

• accessing the r encoded symbols, stored in a first memory;
• performing a first transformation step to compute an operation of a matrix, the operation being an inverse of an encoding matrix, operating on the r encoded symbols to produce an intermediate set of output symbols, at least some of the intermediate set comprising some of the d decoded symbols;
• storing the intermediate set of output symbols in the first memory, replacing at least some of the r encoded symbols, the number of output symbols in the intermediate set being less than the number d;
• and
• repeating the performing and storing steps at least once until the first memory contains at least the d decoded symbols and less than all of the r encoded symbols.

A communication system wherein data arranged as a plurality of k source symbols is transformed at a transmitter into a plurality of n encoded symbols, transmitted over a communication channel and at least some of the transmitted encoded symbols are received at a receiver as a plurality of r received symbols and those r received symbols are transformed into a plurality of d decoded symbols representing the k source symbols when d is not less than k, comprising:

• a transmit buffer having a size such that the size of memory required for the k source symbols and the size of memory required for the n encoded symbols together totals more than the size of the transmit buffer;
• transmit generating logic for generating an intermediate set of output symbols, at least some of the intermediate set comprising some of the n encoded symbols by computing an operation of an encoding matrix operating on the k source symbols;
• transmit storing logic for storing the intermediate set of output symbols in the transmit buffer, replacing at least some of the k source symbols, the number of output symbols in the intermediate set being less than the number n;
• flow logic to cause the transmit generating logic to generate another intermediate set of output symbols and transmit storing logic to store that intermediate set of output symbols, replacing additional ones of the k source symbols, until the transmit buffer contains at least the n encoded symbols and less than all of the k source symbols;
• a transmit circuit for transmitting the n encoded symbols over the communication channel;
• a receive circuit for receiving the r received symbols, wherein the r received symbols are the result of the communication channel conveying the n encoded symbols;
• a receive buffer having a size such that the size of memory required for the r received symbols and the size of memory required for the d decoded symbols together totals more than the size of the receive buffer;
• receive generating logic for generating an intermediate set of receive output symbols, at least some of the intermediate set of receive output symbols comprising some of the d decoded symbols by computing an operation of a decoding matrix operating on the r received symbols;
• receive storing logic for storing the intermediate set of receive output symbols in the receive buffer, replacing at least some of the r received symbols, the number of receive output symbols in the intermediate set of receive output symbols being less than the number d;
• and
• flow logic to cause the receive generating logic to generate another intermediate set of receive output symbols and receive storing logic to store that intermediate set of receive output symbols, replacing additional ones of the r received symbols, until the receive buffer contains at least the d decoded symbols and less than all of the r received symbols.

An encoder that encodes data arranged as a plurality of source symbols into a plurality of encoded symbols, the encoder usable with a storage device or in a transmitter to transmit data to a receiver via a channel, wherein data arranged as a plurality of k source symbols is encoded into a plurality of n encoded symbols, the encoder comprising:

• an encode buffer having a size such that the size of memory required for the k source symbols and the size of memory required for the n encoded symbols together totals more than the size of the encode buffer, thereby introducinga memory constraint;
• generating logic for generating an intermediate set of output symbols from the k source symbols, at least some of the intermediate set comprising some of then encoded symbols, by computing an operation of an encoding matrix operating on the k source symbols;
• storing logic for storing the intermediate set of output symbols in the encode buffer, replacing at least some of the k source symbols previously stored in the encode buffer, wherein the number of output symbols in the intermediate set is less than n;
• and
• flow logic to cause the generating logic to generate an additional intermediate set of output symbols and to cause the storing logic to store the additional intermediate set, replacing additional ones of the k source symbols, until the encode buffer contains at least the n encoded symbols.

A decoder that decodes data arranged as a plurality of encoded received symbols into a plurality of decoded symbols, the decoder usable with a storage device reader or in a receiver that receives data from a transmitter via a channel, wherein data arranged as a plurality of r received symbols is decoded into a plurality of d decoded symbols when d is not less than a number, k, of source symbols encoded by the plurality of r received symbols, the decoder comprising:

• a decode buffer having a size such that the size of memory required for the r received symbols and the size of memory required for the d decoded symbols together totals more than the size of the decode buffer, thereby introducing a memory constraint;
• generating logic for generating an intermediate set of received output symbols from the r received symbols, at least some of the intermediate set comprising some of the d decoded symbols, by computing an operation of a decoding matrix operating on the r received symbols;
• storing logic for storing the intermediate set of output symbols in the decode buffer, replacing at least some of the r received symbols previously stored in the decode buffer, wherein the number of decoded symbols in the intermediate set is less than d;
• and
• flow logic to cause the generating logic to generate an additional intermediate set of received symbols and to cause the storing logic to store the additional intermediate set, replacing additional ones of the r received symbols, until the decode buffer contains at least the d decoded symbols.