On the Maximum Number of Codewords of X-Codes of Constant Weight Three
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2019
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913502380163072 |
|---|---|
| author | Tsunoda, Yu Fujiwara, Yuichiro |
| author_facet | Tsunoda, Yu Fujiwara, Yuichiro |
| contents | X-codes form a special class of linear maps which were originally introduced for data compression in VLSI testing and are also known to give special parity-check matrices for linear codes suitable for error-erasure channels. In the context of circuit testing, an $(m, n, d, x)$ X-code compresses $n$-bit output data $R$ from the circuit under test into $m$ bits, while allowing for detecting the existence of an up to $d$-bit-wise anomaly in $R$ even if up to $x$ bits of the original uncompressed $R$ are unknowable to the tester. Using probabilistic combinatorics, we give a nontrivial lower bound for any $d \geq 2$ on the maximum number $n$ of codewords such that an $(m, n, d, 2)$ X-code of constant weight $3$ exists. This is the first result that shows the existence of an infinite sequence of X-codes whose compaction ratio tends to infinity for any fixed $d$ under severe weight restrictions. We also give a deterministic polynomial-time algorithm that produces X-codes that achieve our bound. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1903_09788 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | On the Maximum Number of Codewords of X-Codes of Constant Weight Three Tsunoda, Yu Fujiwara, Yuichiro Information Theory X-codes form a special class of linear maps which were originally introduced for data compression in VLSI testing and are also known to give special parity-check matrices for linear codes suitable for error-erasure channels. In the context of circuit testing, an $(m, n, d, x)$ X-code compresses $n$-bit output data $R$ from the circuit under test into $m$ bits, while allowing for detecting the existence of an up to $d$-bit-wise anomaly in $R$ even if up to $x$ bits of the original uncompressed $R$ are unknowable to the tester. Using probabilistic combinatorics, we give a nontrivial lower bound for any $d \geq 2$ on the maximum number $n$ of codewords such that an $(m, n, d, 2)$ X-code of constant weight $3$ exists. This is the first result that shows the existence of an infinite sequence of X-codes whose compaction ratio tends to infinity for any fixed $d$ under severe weight restrictions. We also give a deterministic polynomial-time algorithm that produces X-codes that achieve our bound. |
| title | On the Maximum Number of Codewords of X-Codes of Constant Weight Three |
| topic | Information Theory |
| url | https://arxiv.org/abs/1903.09788 |