Linear ensembles of codes (Corresp.)

Abstract
A linear ensemble of codes is defined as one over which the informationK-tuple\proptois encoded as\proptoG \oplus_{z}whereGis equally likely to assume any matrix in a linear space\cal BofKbyNbinary matrices and wherezis independent ofGand equally likely to assume any binaryN-tuple. A technique for upperbounding the ensemble averageP(E)of the probability of error, when the codes of\cal Bare used on the binary symmetric channel with maximum likelihood decoding, is presented which reduces to overbounding a deterministic integer-valued function defined on the space of binaryN-tuples. This technique is applied to the ensemble of K by N binary matrices having for/th row the (i- 1) right cyclic shift of the first, i= 1,2,. . . ,K, and where the first row is equally likely to he any binaryN-tuple. For this ensemble it is shown thatP(E) \leq \mu(N) \exp_{2}-NE_{r}(K/N)whereE_{r}( \cdot)is the random coding exponent for the binary symmetric channel and_{ \mu}(N)is the number of divisors ofX^{N}+ 1. If\cal Bis pairwise independent it is shown that the above technique yields the random coding bound for block codes and that moreover there exists at least one code in the ensemble\cal Bwhose minimum Hamming distance meets a Gilbert-type lower bound.

This publication has 1 reference indexed in Scilit: