On Row-by-Row Coding for 2-D Constraints

A constant-rate encoder-decoder pair is presented for a fairly large family of two-dimensional (2-D) constraints. Encoding and decoding is done in a row-by-row manner, and is sliding-block decodable. Essentially, the 2-D constraint is turned into a set of independent and relatively simple one-dimens...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2009-08, Vol.55 (8), p.3565-3576
Main Authors: Tal, I., Etzion, T., Roth, R.M.
Format: Article
Language:English
Subjects:
Applied sciences
Arrays
Cities and towns
Coders
Codes
Coding, codes
Computer science
Construction
Cryptography
Data encryption
Decoding
Encoders
Encoding
Enumerative coding
Exact sciences and technology
Floating point arithmetic
flow networks
Graphs
Information processing
Information theory
Information, signal and communications theory
Kronecker product
Labeling
Magnetic materials
parallel encoding
Probability distribution
row-by-row coding
runlength-limited (RLL) constraints
Signal and communications theory
Strip
Strips
Telecommunications and information theory
Two dimensional displays
two-dimensional (2-D) constraints
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A constant-rate encoder-decoder pair is presented for a fairly large family of two-dimensional (2-D) constraints. Encoding and decoding is done in a row-by-row manner, and is sliding-block decodable. Essentially, the 2-D constraint is turned into a set of independent and relatively simple one-dimensional (1-D) constraints; this is done by dividing the array into fixed-width vertical strips. Each row in the strip is seen as a symbol, and a graph presentation of the respective 1-D constraint is constructed. The maxentropic stationary Markov chain on this graph is next considered: a perturbed version of the corresponding probability distribution on the edges of the graph is used in order to build an encoder which operates in parallel on the strips. This perturbation is found by means of a network flow, with upper and lower bounds on the flow through the edges. A key part of the encoder is an enumerative coder for constant-weight binary words. A fast realization of this coder is shown, using floating-point arithmetic.
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2009.2023754