A new efficient design of second-order spectralnull (2-OSN) codes is presented. The new codes are obtained by applying the technique used to design parallel decoding balanced (i.e., 1-OSN) codes to the random walk method introduced by some of the authors for designing 2-OSN codes. This gives new non-recursive efficient code designs, which are less redundant than the code designs found in the literature. In particular, if k ∈ IIN is the length of a 1-OSN code then the new 2-OSN coding scheme has length n = k + r ∈ IIN with an extra redundancy of r ≃ 2 log2k + (1/2) log2log2k - 0.174 check bits, with k and r even and n multiple of 4. The whole coding process requires O(k log k) bit operations and O(k) bit memory elements.

A new efficient coding scheme is given for second-order spectral-null (2-OSN) codes. The new method applies the Knuth's optimal parallel decoding scheme for balanced (i.e., 1-OSN) codes to the random walk method introduced by Tallini and Bose to design 2-OSN codes. If k ∈ IN is the length of a 1-OSN code then the new 2-OSN coding scheme has length n = k+r ∈ IN with an extra redundancy of r ≳ 2 log2k + (1/2) log2log2k - 0.674 check bits. The whole coding process requires O(n log n) bit operations and 0(n) bit memory elements.

In an unordered code, no code word is contained in any other code word. Unordered codes are all unidirectional error detecting (AUED) codes. In the binary case, it is well known that among all systematic codes withkinformation bits, Berger codes are optimal unordered codes withr=[log2(k+1)] ≅ log2kcheck bits. This paper gives some new theory on variable length unordered codes and introduces a new class of systematic (instantaneous) unordered codes with variable length check symbols. The average redundancy of the new codes presented here isr≅ (1/2)log2k+c, wherec∈ (1.0470,1.1332) ⊆IRandk∈INis the number of information bits. Whenkis large, it is shown that such redundancy is at most 0.6069 bits off the redundancy of an optimal systematic unordered code design with fixed length information symbols and variable length check symbols; and, at most 2.8075 bits off the redundancy of an optimal variable length unordered code design. The generalization is also given for the nonbinary case and it is shown that similar results hold true.

In an unordered code no codeword is contained in any other codeword. Unordered codes are all unidirectional error detecting (AUED) codes. In the binary case, it is well known that among all systematic codes with k information bits, Berger codes are optimal unordered codes with r = ¿log2(k+1)¿ check bits. This paper gives some new theory on variable length unordered codes and introduces a new class of systematic unordered codes with variable length check symbols. The average redundancy of these new codes is r ¿ (1/2) log2(¿ek/2) = (1/2) log2k + 1.047, where k¿IN is the number of information bits. It is also shown that such codes are optimal in the class of systematic unordered codes with fixed length information symbols and variable length check symbols. The generalization to the non-binary case is also given.