TY - JOUR

T1 - A general method for the development of constrained codes

AU - Ryabko, Boris

PY - 2025/3/18

Y1 - 2025/3/18

N2 - Nowadays there are several classes of constrained codes intended for different applications. The following two large classes can be distinguished. The first class contains codes with local constraints; for example, the source data must be encoded by binary sequences containing no sub-words 00 and 111. The second class contains codes with global constraints; for example, the code-words must be binary sequences of certain even length where half of the symbols are zeros and half are ones It is important to note that often the necessary codes must fulfill some requirements of both classes. In this paper we propose a general polynomial complexity method for constructing codes for both classes, as well as for combinations thereof. The proposed method uses the Cover enumerative code, but calculates all the parameters on the fly with polynomial complexity, unlike the known applications of that code which employ combinatorial formulae. The main idea of the paper is to use dynamic programming to perform calculations like: how many sequences with a given prefix and a given suffix length satisfying constraints exist. For the constraints under consideration, we do not need to know the entire prefix, but much less knowledge about the prefix is sufficient. That is, we only need a brief description of the prefix.

AB - Nowadays there are several classes of constrained codes intended for different applications. The following two large classes can be distinguished. The first class contains codes with local constraints; for example, the source data must be encoded by binary sequences containing no sub-words 00 and 111. The second class contains codes with global constraints; for example, the code-words must be binary sequences of certain even length where half of the symbols are zeros and half are ones It is important to note that often the necessary codes must fulfill some requirements of both classes. In this paper we propose a general polynomial complexity method for constructing codes for both classes, as well as for combinations thereof. The proposed method uses the Cover enumerative code, but calculates all the parameters on the fly with polynomial complexity, unlike the known applications of that code which employ combinatorial formulae. The main idea of the paper is to use dynamic programming to perform calculations like: how many sequences with a given prefix and a given suffix length satisfying constraints exist. For the constraints under consideration, we do not need to know the entire prefix, but much less knowledge about the prefix is sufficient. That is, we only need a brief description of the prefix.

UR - https://www.mendeley.com/catalogue/6ae7b524-dc94-3cdb-a07d-655501200850/

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-105000544710&origin=inward&txGid=049893a27340d6c01259d65eec2a763b

U2 - 10.1109/TIT.2025.3552660

DO - 10.1109/TIT.2025.3552660

M3 - Article

SP - 1

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

ER -