Method and apparatus for fast encoding of data symbols according to half-weight codes
AssigneeDigital Fountain, Inc.
InventorsMichael Luby, M. Amin Shokrollahi
Life of this patent
Estimating the term…
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).
Claims6
A method of encoding data for transmission from a source to a destination over a communications channel using an encoder having an input to receive signals representative of a plurality of input symbols and an output for a plurality of encoded output symbols, wherein the plurality of input symbols are encoded into the plurality of encoded output symbols using a half-weight code comprising:
- accessing a set of k input symbols;
- generating redundant symbols from at least some of the set of k input symbols, including a plurality of h Half-Weight symbols using on the order of (3·(k−1))+(log2(k)/2)+1XOR symbol operations, where h is on the order of log(k);
- and
- generating encoded symbols from at least the redundant symbols including the plurality of h Half-Weight symbols, using a dynamic encoder that generates encoded symbols as needed.
Dependencies are inferred from the claim text.