Pick a (n −k)×n matrix H over Fq at random. Show that with high probability the code whose parity check matrix is H achieves the GV bound.中文回答
时间: 2024-03-15 16:42:00 浏览: 17
这个问题是关于随机选择矩阵H来构建校验矩阵的码字,使其达到GV界的概率的问题。根据GV界定理,对于给定的码长n,信息位长度k和有限域Fq,存在一个下界,使得任何线性码的最小距离d都满足d≥n-k+1-√k(q-1)。因此,我们的目标是构建一个校验矩阵H,使得对应的线性码的最小距离不小于这个下界。
首先,我们需要计算随机选择矩阵H的概率,使得对应的线性码的最小距离小于GV界。我们可以使用概率论和线性代数的知识来解决这个问题。具体来说,我们需要计算任意两行之间的内积为0的概率,记为P。根据随机矩阵的性质,我们可以假设每个元素都是独立且均匀分布在有限域Fq上的随机变量。因此,对于任意两行i和j(i≠j),它们的内积为0的概率为:
P(i,j)=Pr(H_{i,1}H_{j,1}+...+H_{i,n}H_{j,n}=0)
由于每个元素都是独立的,因此可以将上式展开为:
P(i,j)=∏_{t=1}^{n} Pr(H_{i,t}H_{j,t}=0)
由于H_{i,t}和H_{j,t}都是随机变量,它们的乘积为0的概率为:
Pr(H_{i,t}H_{j,t}=0)=1-1/q
因此,我们有:
P(i,j)=(1-1/q)^k
根据上述计算,我们可以得到任意两行之间的内积为0的概率P。然后,我们可以计算对于给定的码长n和信息位长度k,任意两行之间的内积为0的期望数量E。具体来说,我们有:
E={n \choose 2} P={n \choose 2} (1-1/q)^k
如果E足够小,那么我们可以说对于大多数随机矩阵H,其对应的线性码的最小距离都不小于GV界。具体来说,当E<1时,我们可以说概率接近于1,当E<1/2时,我们可以说概率大于1/2。
因此,我们需要解决的问题是计算E是否小于1或1/2。具体来说,我们有:
E={n \choose 2} (1-1/q)^k
因此,我们需要计算(1-1/q)^k是否小于1/n(n-1)或1/2n(n-1)。根据二项式定理,我们有:
(1-1/q)^k=\sum_{i=0}^{k} (-1)^i {k \choose i} 1/q^i
由于我们要计算的是(1-1/q)^k的下界,因此我们只需要计算上述求和式中i=k或i=k-1的项。具体来说,当i=k时,我们有:
(-1)^k {k \choose k} 1/q^k=1/q^k
当i=k-1时,我们有:
(-1)^{k-1} {k \choose k-1} 1/q^{k-1}=(-1)^{k-1} k/q^{k-1}
因此,我们可以得到:
(1-1/q)^k≥1/q^k-kq^{-k+1}
当E小于1时,我们需要满足:
E={n \choose 2} (1-1/q)^k<1
代入上式,我们有:
{n \choose 2} (1-1/q)^k<{n \choose 2}/q^k-kq^{-k+1}<1
因此,我们需要满足:
q^k-kq^{-k+1}>{n \choose 2}
当E小于1/2时,我们需要满足:
E={n \choose 2} (1-1/q)^k<1/2
代入上式,我们有:
{n \choose 2} (1-1/q)^k<{n \choose 2}/(2q^k-kq^{-k+1})<1/2
因此,我们需要满足:
q^k-kq^{-k+1}>{n \choose 2}/(2-1/q^k)
综上所述,我们可以通过计算上述不等式来确定随机选择矩阵H的概率,使得对应的线性码的最小距离不小于GV界。如果上述不等式成立,则我们可以说对于大多数随机矩阵H,其对应的线性码的最小距离都不小于GV界,这就是所谓的“高概率”情况。