Method and apparatus for encoding and decoding unordered error correcting codes

摘要

An unordered error correcting code is constructed by an encoding method and apparatus that accepts k bits of information and is capable of providing unordered ECC codewords. All pairs of these codewords are at least a distance d apart, where d>=(2t+1) and t is the maximum number of errors correctable by the code. The k bits of information are encoded with an ECC encoding algorithm to produce ECC codewords that are at least distance d apart. The least number of tail bits required to produce the unordered ECC codewords is appended to each of the ECC codewords. The tail bits for each codeword are constructed by dividing its weight by d for determining the integer part of the resulting quotient, generating a binary representation of the value of its integer part, and complementing said binary representation. A noisy received version of the ECC codeword with tail bits truncated is decoded and a preselected error correcting algorithm is applied to correct t1 actual errors and produce a decoded ECC codeword. Tail bits corresponding to the decoded ECC codeword are generated and compared with segregated tail bits for the noisy received ECC codeword for determining the number t2 of errors actually detected. The k information bits derived from the decoded ECC codeword are outputted when (t1+t2)<=t.