UA MATH636 信息論9 Reed-Solomon Code

• Reed-Solomon Code的構(gòu)造
• • 一個(gè)例子

先介紹一類code，maximum distance separable code (MDS code)。考慮一個(gè)$(n,k,d)$-code，之前我們討論的都是$d$最小能是多少，下面來討論一下給定$(n,k)$最大的distance能有多少？之所以想要最大的$d$是因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$d$越大能correct的error就越多。

Singleton Bound給出了線性碼的$d$的上界：$d\le n?k+1$
證明
假設(shè)codebook的alphabet size為$q$，則一共有$q^k$中不同的code。刪除每一個(gè)code的前$d?1$個(gè)符號(hào)，則剩下的code長(zhǎng)度為$n?(d?1)$，根據(jù)$d$的含義，剩下的這個(gè)codebook每?jī)蓚€(gè)code至少也有一個(gè)符號(hào)不同，而長(zhǎng)度為$n?(d?1)$的code最多有$q^{n?(d?1)}$種，因此
$$q^k\le q^{n?(d?1)}$$
根據(jù)這個(gè)關(guān)系可以得到Singleton Bound。

MDS code就是$d=n?k+1$的code system。

Reed-Solomon Code的構(gòu)造

考慮MDS code $(n,k,n?k+1)$，滿足$k\le n\le p$。則message vector為
$$m=[x_1,?,x_k],x_i\in GF(p),i=1,?,k$$
我們可以用定義在Galois域上的多項(xiàng)式來表示這個(gè)message：
$$P(t)=\sum _{i=1}^k{x}_i{t}^{i?1}$$
然后我們用這個(gè)多項(xiàng)式來編碼：
$$c=[c_1,?,c_n]=[P(0),P(1),?,P(n?1)]$$
其實(shí)更一般的，只需要選擇$n$個(gè)不同的數(shù)值就可以了，比如${\alpha }_0,?,{\alpha }_{n?1}\in GF(p)$
$$c=[c_1,?,c_n]=[P({\alpha }_0),P({\alpha }_1),?,P({\alpha }_{n?1})]$$

性質(zhì)1 RS code是線性碼
$[P(0),P(1),?,P(n?1)]$可以用message vector乘以Vandermonde矩陣來表示，定義生成矩陣為
$$G=V(0,1,2,?,n{)}^T$$
則
$$c=mG$$

性質(zhì)2 RS code是MDS code
假設(shè)$a$是$P(t)$的一個(gè)根，則$t?a$是$P(t)$的一個(gè)因式。如果$P(t)$有$k?1$個(gè)根，則$P(t)$的階至少為$k?1$。現(xiàn)在考慮$d$，它是所有code的Hamming weight的最小值。所以我們要考慮的是$c=[P({\alpha }_0),P({\alpha }_1),?,P({\alpha }_{n?1})]$中能有幾個(gè)數(shù)字不為0。因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$P(t)$的階數(shù)是$k?1$，也就是說$c$中最多有$k?1$個(gè)零，也就是說最小的Hamming weight是$n?(k?1)$。

一個(gè)例子

考慮$GF(7)$上的(4,2)-RS code，這種code一共有$7^2=49$種，它們的生成矩陣是
$$G=\left[\begin{array}{cccc}1& 1& 1& 1\\ 0& 1& 2& 3\end{array}\right]$$
假設(shè)message vector是$[1,2]$（信源編碼器的輸出），它的RS-code就是
$$mG=[1350]$$（噪聲信道的輸入）。假設(shè)噪聲信道的輸出為$R=[2,3,4,0]$，因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$d=n?k+1=3$，所以這個(gè)RS-code最多可以改掉$(d?1)/2=1$個(gè)error，經(jīng)過噪聲信道傳輸后正好出現(xiàn)了一個(gè)error，所以在解碼的時(shí)候這個(gè)error可以被改掉。

總結(jié)

以上是生活随笔為你收集整理的UA MATH636 信息论9 Reed-Solomon Code的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。