Concatenated codes: serial and parallel

An analogy is examined between serially concatenated codes and parallel concatenations whose interleavers are described by bipartite graphs with good expanding properties. In particular, a modified expander code construction is shown to behave very much like Forney's classical concatenated codes, though with improved decoding complexity. It is proved that these new codes achieve the Zyablov bound /spl delta//sub Z/ on the minimum distance. For these codes, a soft-decision, reliability-based, linear-time decoding algorithm is introduced, that corrects any fraction of errors up to almost /spl delta//sub Z//2. For the binary-symmetric channel, this algorithm's error exponent attains the Forney bound previously known only for classical (serial) concatenations.     

On expander codes

Sipser and Spielman (see ibid., vol.42, p.1717-22, Nov. 1996) have introduced a constructive family of asymptotically good linear error-correcting codes-expander codes-together with a simple parallel algorithm that will always remove a constant fraction of errors. We introduce a variation on their decoding algorithm that, with no extra cost in complexity, provably corrects up to 12 times more errors     

Copyright protection for digital data

If Γ_p is a p-ary code of length n, and a and b are two codewords, then c is called a descendant of a and b if c_i ∈{a_i, b_i} for i=1,…,n. We are interested in codes Γ_p with the property that for any two codewords a and b their only descendant codewords are a and b themselves. This way a coalition of two users who are given codewords a and b cannot frame a third user who is given the codeword c. Intersecting codes over primary field GF(p) with the above mentioned property are found     

Distance properties of expander codes

The minimum distance of some families of expander codes is studied, as well as some related families of codes defined on bipartite graphs. The weight spectrum and the minimum distance of a random ensemble of such codes are computed and it is shown that it sometimes meets the Gilbert-Varshamov (GV) bound. A lower bound on the minimum distances of constructive families of expander codes is derived. The relative minimum distance of the expander code is shown to exceed the product bound, i.e., the quantity /spl delta//sub 0//spl delta//sub 1/ where /spl delta//sub 0/ and /spl delta//sub 1/ are the minimum relative distances of the constituent codes. As a consequence of this, a polynomially constructible family of expander codes is obtained whose relative distance exceeds the Zyablov bound on the distance of serial concatenations.     

The threshold probability of a code

We define and estimate the threshold probability &thetas; of a linear code, using a theorem of Margulis (1974) originally conceived for the study of the probability of disconnecting a graph. We then apply this concept to the study of the erasure and Z-channels, for which we propose linear coding schemes that admit simple decoding. We show that &thetas; is particularly relevant to the erasure channel since linear codes achieve a vanishing error probability as long as p⩽&thetas;, where p is the probability of erasure. In effect, &thetas; can be thought of as a capacity notion designed for codes rather than for channels. Binomial codes haven the highest possible &thetas; (and achieve capacity). As for the Z-channel, a subcapacity is derived with respect to the linear coding scheme. For a transition probability in the range ]log (3/2); 1[, we show how to achieve this subcapacity. As a by-product we obtain improved constructions and existential results for intersecting codes (linear Sperner families) which are used in our coding schemes     

Intersecting codes and independent families

A binary intersecting code is a linear code with the property that any two nonzero codewords have intersecting supports. These codes appear in a wide variety of contexts and applications, e.g., multiple access, cryptography, and information theory. This paper is devoted partly to the study of intersecting codes, and partly to their use in constructing large t-independent families of binary vectors. The latter subject has by now been extensively studied and has application in VLSI testing, defect correction, E-biased probability spaces, and derandomization. By concatenation methods we construct codes with the highest known fate asymptotically. We then generalize the concept to t-wise intersecting codes: we give bounds on the achievable rate of such codes, both existential and constructive. We show how t-wise intersecting codes can be used to obtain (t+1)-independent families. With this method we obtain improved asymptotical constructions of t-independent families. Complexity issues are discussed