Search

The bit stuffing algorithm is a technique for coding constrained sequences by the insertion of bits into an arbitrary data sequence. This approach was previously introduced and applied to (d, k) constrained codes. Results show that the maximum average rate of the bit stuffing code achieves capacity when k = d + 1 or k = [infinity] while it is suboptimal for all other (d, k) pairs. Furthermore, this technique was generalized to produce codes with an average rate that achieves capacity for all (d, k) pairs. However, this extension results in a more complicated scheme. This correspondence proposes a modification to the bit stuffing algorithm that maintains its simplicity. We show analytically that the proposed algorithm achieves improved average rates over bit stuffing for most (d, k) constraints. We further determine all constraints for which this scheme produces codes with an average rate equal to the Shannon capacity. Index Terms--Bit-stuffing encoder, (d, k)-constrained systems, Shannon capacity.

A constrained system is presented by a finite-state labeled graph. For such systems, we focus on block-type-decodable encoders, comprising three classes known as block, block-decodable, and deterministic encoders. Franaszek gives a sufficient condition which guarantees the equality of the optimal rates of block-decodable and deterministic encoders for the same block length. In this paper, we introduce another sufficient condition, called the straight-line condition, which yields the same result. Run-length limited RLL(d, k) and maximum transition run MTR(j, k) constraints are shown to satisfy both conditions. In general, block-type-decodable encoders are constructed by choosing a subset of states of the graph to be used as encoder states. Such a subset is known as a set of principal states. For each type of encoder and each block length, a natural problem is to find a set of principal states which maximizes the code rate. We show how to compute the asymptotically optimal sets of principal states for deterministic encoders and how they are related to the case of large but finite block lengths. We give optimal sets of principal states for MTR(j, k)-block-type-decodable encoders for all code-word lengths. Finally we compare the code rate of nonreturn to zero inverted (NRZI) encoders to that of corresponding nonreturn to zero (NRZ) and signed NRZI encoders. Index Terms--Constrained system, maximum transition run system, precoding, principal states, run-length-limited (RLL) system.

A new interpretation of transform coding is developed that downplays quantization and emphasizes entropy coding, allowing a comparison of entropy coding methods with different memory requirements. With conventional transform coding, based on computing Karhunen--Loeve transform coefficients and then quantizing them, vector entropy coding can be replaced by scalar entropy coding without an increase in rate. Thus the transform coding advantage is a reduction in memory requirements for entropy coding. This paper develops a transform coding technique where the source samples are first scalar-quantized and then transformed with an integer-to-integer approximation to a nonorthogonal linear transform. Among the possible advantages is to reduce the memory requirement further than conventional transform coding by using a single common scalar entropy codebook for all components. The analysis shows that for high-rate coding of a Gaussian source, this reduction in memory requirements comes without any degradation of rate-distortion performance. Index Terms--Entropy coding, Gaussian sources, memory reduction, transform coding.