Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2019
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/1903.09788 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _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 |