Method and apparatus for fast encoding of data symbols according to half-weight codes

Abstract

Efficient methods for encoding and decoding Half-Weight codes are disclosed and similar high density codes are disclosed. The efficient methods require at most 3·(k−1)+h/2+1 XORs of symbols to calculate h Half-Weight symbols from k source symbols, where h is of the order of log(k).

1 . In a decoder having an input to receive signals representative of a plurality of received symbols representing a transmitted signal encoding a plurality of source symbols, the encoding including coding according to a Half-Weight code, wherein a sequence of the source symbols and h Half-Weight symbols are included in the source symbols and the decoder is in a state wherein some of the sequence of source symbols and Half-Weight symbols are missing symbols and some are received symbols, a method of removing dependencies of the Half-Weight symbols on received source symbols in a process of decoding, comprising:
 decoding source symbols from received symbols using a dynamic decoder; and   performing on the order of 3·(k−1)+log(k)/2+1 XOR symbol operations to remove the dependencies of the Half-Weight symbols on the received source symbols, where h is of the order of log(k) and k is the number of input symbols to be recovered.   
   
   
       2 . The method of  claim 1 , wherein the number of XOR symbol operations is not greater than a predetermined constant times k+h. 
   
   
       3 . The method of  claim 1 , further comprising a solving process as part of the process of decoding wherein the solving process comprises solving for the missing source symbols based on the received Half-Symbols, after the dependencies of the received Half-Symbols on the received source symbols have been removed in the performing step. 
   
   
       4 . The method of  claim 1 , wherein dependencies from more than one set of Half-Weight symbols are removed in parallel. 
   
   
       5 . The method of  claim 1 , wherein the dynamic decoder is a chain reaction decoder capable of recovering source symbols from received symbols when source symbols are generated by a fountain encoder and the received symbols are allocated among a set of distinct encoded symbols greater than a number of symbols that would be expected given expected transmission conditions and number of input symbols to recover.