Bit-stuffing algorithms and analysis for run-length constrained channels in two and three dimensions

Author

Nagy, Zsigmond ; Zeger, Kenneth

Author_Institution

Dept. of Electr. & Comput. Eng., Univ. of California, San Diego, CA, USA

Volume

50

Issue

12

fYear

2004

Firstpage

3146

Lastpage

3169

Abstract

A rigorous derivation is given of the coding rate of a variable-to-variable length bit-stuffing coder for a two-dimensional (1,∞)-constrained channel. The coder studied is "nearly" a fixed-to-fixed length algorithm. Then an analogous variable-to-variable length bit-stuffing algorithm for the three-dimensional (1,∞)-constrained channel is presented, and its coding rate is analyzed using the two-dimensional method. The three-dimensional coding rate is demonstrated to be at least 0.502, which is proven to be within 4% of the capacity.

Keywords

binary sequences; runlength codes; source coding; telecommunication channels; variable length codes; bit allocation; bit-stuffing algorithms; fixed-to-fixed length algorithm; lossy source coding; run-length constrained channels; three-dimensional coding rate; transform coding; variable-to-variable length codes; Algorithm design and analysis; Arithmetic; Binary sequences; Channel capacity; Constraint theory; Data storage systems; Mathematical analysis; Quantization; Source coding; Transform coding; 65; Bit allocation; lossy source coding; quantization; transform coding;

fLanguage

English

Journal_Title

Information Theory, IEEE Transactions on

Publisher

ieee

ISSN

0018-9448

Type

jour

DOI

10.1109/TIT.2004.838112

Filename

1362903