Coding for the ℓ∞-limited permutation channel
Coding for the ℓ∞-limited permutation channel
复制标题
ℓ∞ 有限排列通道的编码
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Eitan Yaakobi
中科院分区：
文献类型：
--
作者：
M. Langberg;Moshe Schwartz;Eitan Yaakobi
在这项工作中，我们认为在存在同步错误的信息通信。具体地，我们考虑置换信道，其中发送的码字x =（<sub>x1</sub>，...，<sub>xn</sub>）被置换π ∈<sub>Sn破坏</sub>以产生接收字y =（<sub>y1</sub>，...，<sub></sub>其中<sub>yi</sub>= x<sub>π（i）</sub>。我们开始研究置换信道上的最坏情况（或零错误）通信，该信道通过应用置换π来扭曲信息，该置换π被限制为将任何符号移位至多r个位置，即在π<sub>∞</sub>度量中具有至多r个权重的置换π。我们提出了直接和递归的结构，以及二进制和一般字母表的速度上的限制。特别注意r = 1的情况。
In this work we consider the communication of information in the presence of synchronization errors. Specifically, we consider permutation channels in which a transmitted codeword x = (x<sub>1</sub>, ..., x<sub>n</sub>) is corrupted by a permutation π ∈ S<sub>n</sub> to yield the received word y = (y<sub>1</sub>, ..., y<sub>n</sub>) where y<sub>i</sub> = x<sub>π(i)</sub>. We initiate the study of worst case (or zero error) communication over permutation channels that distort the information by applying permutations π which are limited to displacing any symbol by at most r locations, i.e. permutations π with weight at most r in the ℓ<sub>∞</sub>-metric. We present direct and recursive constructions, as well as bounds on the rate of such channels for binary and general alphabets. Specific attention is given to the case of r = 1.