RS碼編碼算法

2024年2月15日發(作者：餐飲員工培訓)

- -

RS碼編碼算法

一．RS編碼

對于能夠糾正t個錯誤的RS（n,k,d）碼，具有如下特征：

1） 碼長：n?2m?1符號或m(2m?1)比特

2） 信息碼元數：k?n?2t或mk比特；

3） 監督碼元數：n?k?2t符號或m(n?k)比特；

4） 最小距離：d?2t?1?n?k?1符號或m(n?k?1)比特；

最小距離為d的本原RS碼的生成多項式為

g(x)?(x??)(x??2)(x??3)?(x??d?2)

式中的m是一個任意整數。

令信息元多項式為：

m(x)?m0?m1?m2x2???mk?1xk?1

二．RS編碼器的類型

1．基于乘法形式的RS編碼器

公式：c(x)?m(x)g(x)

結構圖如下：

由上面結構的乘法編碼器輸出的碼字是非系統碼。

2．基于除法形式的RS編碼器

（1） 根據生成多項式g(x)構造的除法編碼器。

令

xn?ka(x)r(xg(x)?b(x)?)g(x)

剩余多項式r(x)至少比g(x)低一次。

r(x)?r2t?1x2t?1?r2t?2x2t?2???r2x2?r1x?r0

-

總結

- -

則編程的碼多項式為

c(x)?xn?ka(x)?r(x)?cn?1x具體實現如下圖：

n?1?cn?2xn?2???c2x?c1x?c02

（2） 根據校驗碼多項式h(x)構造的除法編碼器

設校驗多項式為：

h(x)?hkx?hk?1x系統碼的多項式為：

kk?1???h1x?h0

C(x)?cn?1xn?1?cn?2xn?2???cn?kxn?k?cn?k?1xn?k?1???c1x?c0它的前k位系數：cn?1,cn?2,?,cn?k是已知的信息位，而后n?k位系數：cn?k?1,cn?k?2,?,c1,c0是需求的校驗位。碼多項式必是生成多項式g(x)的背式，所以

C(x)?q(x)g(x)

??C(x)?n?1,??g(x)?n?k,??q(x)?k?1

而

h(x)C(x)?q(x)g(x)h(x)?q(x)(xn?1)?q(x)xn?q(x)

由于

??C(x)?n?1,??g(x)?n?k,??g(x)?n?k,??q(x)?k?1

所以q(x)x的最低位次數至少為n次，而在h(x)C(x)的乘積中nxn?1,xn?2,?,xk的次數為0。

xn?1的系數：

-

總結

- -

cn?1?0h0?cn?1?1h1???cn?1?khk

xn?2的系數：

cn?2?0h0?cn?2?1h1???cn?2?khk

而

?cn?i?jhj?0j?0ki?0,1,2,?,n?k

由于h(x)為首一多項式，hk?1，故上式可寫為

cn?k?i???cn?i?jhjj?0k?1i?1,2,?,n?k

上式展開為：

cn?k?1??(cn?1h0?cn?2h1???cn?khk?1)cn?k?2??(cn?2h0?cn?3h1???cn?k?1hk?1)?cn?k?(n?k)?c0??(ckh0?ck?1h1???c1hk?1)由上式看出碼字C的第一個碼元cn?k?1可由k個信息元cn?1,cn?2,?,cn?k與

h(x)的系數相乘得到，而由cn?2,cn?3,?,cn?k,cn?k?1可得到第二個校驗元cn?k?2，再由cn?3,?,cn?k信息元和第一、第二校驗元cn?k?1,cn?k?2可得到第三校驗元cn?k?3。按這樣的線性關系遞推，一直可求得所有的n?k個校驗元cn?k?1,cn?k?2,?,c1,c0。

具體實現如下圖：

（3） RS的時域編碼實際例子

-

總結

- -

RS碼是非二進制碼，它是在GF(q)上的，這里q?2。這里我們選用GF(16)域來進行，域中16個元素可用4bits符號表示。

例 構造一個能糾正3個錯誤符號，碼長為15，m=4的RS碼。求生成多項式和編碼電路。

解：當t?3時，最小碼距Dmin?7，信息元長度k?9。該碼為（15，9）RS碼，其生成多項式為：

g(x)?(x?a)(x?a2)(x?a3)(x?a4)(x?a5)(x?a6?x?ax?ax?ax?ax?ax?a2461

由分圓多項式多項式：

g(x)?(x?x?1)(x?x?1)

a?GF(16)是本原域元素，它是多項式x4?x?1的根，則

a4?a?1?0

或

a?a?1

4以x?x?1為模的GF(2)的元素如下表：

44

a0?1

0001

a8?a2?1

0010

a9?a3?a

0100

a10?a2?a?1

1000

a11?a3?a2?a

0101

1010

0111

1110

a

a2

a3

a4?a?1

0011

a12?a3?a2?a?1

1111

0110

a13?a3?a2?1

1100

a14?a3?1

1101

1001

0001

a5?a2?a

a6?a3?a2

a7?a3?a?1

1011

a15?1

GF(24)中每個元素都可表示成它的自然基地1,a,a2,a3（在域GF(2)上）的線性組合，如下形式：

-

總結

- -

a3a?a2a?a1a?a0

因此在GF(2)上的2進制RS碼，它的編碼電路可用k或n?k級2進制寄存器實現。本例是用n?k?6級乘法器電路實現，如下圖。圖中的移位積存器必須是由能積存16進制的元件組成，這可用4級觸發器組成的移存器完成。44432a10,a14,a4,a6,a9常乘器可用模2加法器構成。

在域GF(2)上的系數a,a,a,a,a可用自然基地表示為如下形式：

41014469a10(a3a3?a2a2?a1a?a0)?a3a13?a2a12?a1a11?a0a10?a3(a3?a2?1)?a2(a3?a2?a?1)?a1(a3?a2?a)?a0(a2?a?1)

?(a3?a2?a1)a3?(a3?a2?a1?a0)a2?(a2?a1?a0)a?(a2?a0)

a14(a3a3?a2a2?a1a?a0)?a3a17?a2a16?a1a15?a14?a0a?a3a?a2a?(a1?a0)

32

a4(a3a3?a2a2?a1a?a0a0)?a3a7?a2a6?a1a5?a0a4?a3(a3?a?1)?a2(a3?a2)?a1(a2?a)?a0(a?1)?(a3?a2)a3?(a2?a1)a2?(a3?a1?a0)a?(a3?a0)

a6(a3a3?a2a2?a1a?a0)?a3a9?a2a8?a1a7?a0a6?a3(a3?a)?a2(a2?1)?a1(a3?a?1)?a0(a3?a2)?(a3?a1?a0)a3?(a2?a0)a2?(a3?a1?a0)a?(a2?a1)

-

總結

- -

a9(a3a3?a2a2?a1a?a0)?a3a12?a2a11?a1a10?a0a9?a3(a3?a2?a?1)?a2(a3?a2?a)?a1(a2?a?1)?a0(a3?a)?(a3?a2?a0)a3?(a3?a2?a1)a2?(a3?a2?a1?a0)a?(a3?a1)

GF(24)中乘a10的轉換電路如下表示：

a10(a3a3?a2a2?a1a?a0)?(a3?a2?a1)a?(a3?a2?a1?a0)a?(a2?a1?a0)a?(a2?a0)式中：a3'?a3?a2?a1

a2'?a3?a2?a1?a0

32

a1'?a2?a1?a0

a0'?a2?a0

GF(214)中乘a10電路

GF(24)中乘a14的轉換電路如下表示：

a3'?a3?a2

a2'?a2?a1

a1'?a3?a1?a0

a0'?a1?a0

GF(214)中乘a14電路

-

總結

- -

GF(24)中乘a4的轉換電路如下表示：

a3'?a0

a2'?a3

a1'?a2

a0'?a3?a0

GF(214)中乘a14電路

GF(24)中乘a6的轉換電路如下表示：

a3'?a3?a1?a0

a2'?a2?a0

a1'?a3?a1?a0

a0'?a2?a1

GF(214)中乘a6電路

GF(24)中乘a9的轉換電路如下表示：

a3'?a3?a2?a0

a2'?a3?a2?a1

a1'?a3?a2?a1?a0

a0'?a3?a1

-

總結

- -

GF(214)中乘a9電路

[15,9,7]RS編碼器具體實現電路如下圖所示：

工作過程如下：

（1） 門打開，開關撥到符號輸入端，所有移存器清0。然后將6個16進制信息符號，一邊送入移存器，一邊送入信道。注意每一節拍移動一個16進制符號。

（2） 6個16進制符號送入移存器后，完成除法運算，移存器中的就是余式。此時，門關閉，開關撥到下面。再經過6個節拍的移動，得到所有6個校驗元，并且跟隨信息元送入信道，完成一個碼字的編碼過程。

（3） 清洗積存器，打開門，開始第二組信息元的編碼。

-

總結