论文标题
独特的邻居代码的范围
Bounds on Unique-Neighbor Codes
论文作者
论文摘要
回想一下，长度$ n $的二进制线性代码是线性子空间$ \ mathcal {c} = \ {x \ in \ mathbb {f} _2 _2^n \ mid ax = 0 \} $。在这里，均等检查矩阵$ a $是二进制$ m \ times n $ n $等级$ m $。我们说$ \ MATHCAL {C} $具有费率$ r = 1- \ frac Mn $。它的距离，表示为$Δn$是$ \ Mathcal {C} $中非零向量的最小的锤击权重。二进制线性代码的速率与\ \ \ \距离问题是编码理论中的基本开放问题，也是离散数学中的一个有趣的问题。它涉及函数$ r_l（δ）$，这是给定$ 0 \leδ\ le1 $的最大速率$ r $和任意大的长度$ n $。在这里，我们调查了下一步描述的这个基本问题的变体。 显然，$ \ MATHCAL {C} $具有距离$Δn$，并且仅当$ 0 <n'<Δn$时，每$ M \ times n'$ subbastrix of $ a $ a $ a $都有一排奇数。在编码理论中的几个问题中，我们说$ a $具有带有参数$Δn$的唯一邻居属性，如果每个此类subpatrix都有一排重量$ 1 $。令$ r_u（δ）$为具有奇偶校验检查矩阵的线性代码的最大可能的渐近率，具有更强的属性。显然，$ r_u（\ cdot），r_l（\ cdot）$是非侵入功能，所有$δ$的$ r_u（δ）\ le r_l（δ）$。此外，$ r_u（0）= r_l（0）= 1 $，$ r_u（1）= r_l（1）= 0 $，因此，让$ 0 \leuΔ_U\leΔ_L\ le1 $是$ r_u $ r_u $ resp。众所周知，$δ_l= \ frac12 $，我们推测$Δ_U$严格小于$ \ frac12 $，即具有独特邻居属性的线性代码速率更严格地限制了。虽然猜想保持开放，但我们在这里证明了几个支持它的结果。 假定读者在编码理论中没有任何特定的背景，但我们偶尔指出了来自该领域的一些相关事实。
Recall that a binary linear code of length $n$ is a linear subspace $\mathcal{C} = \{x\in\mathbb{F}_2^n\mid Ax=0\}$. Here the parity check matrix $A$ is a binary $m\times n$ matrix of rank $m$. We say that $\mathcal{C}$ has rate $R=1-\frac mn$. Its distance, denoted $δn$ is the smallest Hamming weight of a non-zero vector in $\mathcal{C}$. The rate vs.\ distance problem for binary linear codes is a fundamental open problem in coding theory, and a fascinating question in discrete mathematics. It concerns the function $R_L(δ)$, the largest possible rate $R$ for given $0\leδ\le1$ and arbitrarily large length $n$. Here we investigate a variation of this fundamental question that we describe next. Clearly, $\mathcal{C}$ has distance $δn$, if and only if for every $0<n'<δn$, every $m\times n'$ submatrix of $A$ has a row of odd weight. Motivated by several problems from coding theory, we say that $A$ has the unique-neighbor property with parameter $δn$, if every such submatrix has a row of weight $1$. Let $R_U(δ)$ be the largest possible asymptotic rate of linear codes with a parity check matrix that has this stronger property. Clearly, $R_U(\cdot),R_L(\cdot)$ are non-increasing functions, and $R_U(δ)\le R_L(δ)$ for all $δ$. Also, $R_U(0)=R_L(0)=1$, and $R_U(1)=R_L(1)=0$, so let $0\leδ_U \leδ_L\le1$ be the smallest values of $δ$ at which $R_U$ resp.\ $R_L$ vanish. It is well known that $δ_L=\frac12$ and we conjecture that $δ_U$ is strictly smaller than $\frac12$, i.e., the rate of linear codes with the unique-neighbor property is more strictly bounded. While the conjecture remains open, we prove here several results supporting it. The reader is not assumed to have any specific background in coding theory, but we occasionally point out some relevant facts from that area.
