4・1   シフトレジスタ を 使った 符号器, 復号器

線形符号 は、パリティ検査行列 H に対し

        H w ^T = 0     ――― (4・1)

を 満足する 符号 である。符号器 では、式(4・1) を 満足する 符号語 w を 通報 i から 次式 で 作り、通信路 に 出す。

        w = i G     ――― (4・2)

復号器 では 受信語 y から シンドローム

        s = H y ^T     ――― (4・3)

を 計算し、s に従い 誤りの検出・訂正 を行う。 3章 で 紹介した 符号器, 復号器 は 並列器 の 符号器, 復号器 と 呼ばれる。 この回路 は 高速であるが、符号長 n や 情報点数 k が 増えると 回路の規模 が 大きくなる欠点 を もつ。 ある種 の 線形符号 においては 式(4・2), (4・3) の 計算 が シフトレジスタ により 行え、符号器, 復号器 が 簡単 となる。 そのような 符号 として 巡回符号 がある。 以下、この節では ハミング (7, 4) 巡回符号 を 例に 説明 を 行う。

[1]   シンドロームの計算式

3・2節 [3]項 の 例3c の H 行列

を少し変形した、次のパリティ検査行列 H' を使う。

ここで、α⁶ , ... , α⁰ は h₁ , ... , h₇ と同じく各列ベクトルを表している記号であり、肩の添え字 ⁶ , ... , ⁰ は 行列 H ' の列の番号であると、とりあえず理解していただきたい。

式(4・5) の H ' も組織符号を与える。H と H ' の違いは P と P ' の部分であり、1列目の列ベクトル h₁ が4番目の α³ , h₂ が α⁶ , ... と順番が入れ替わっているだけである。パリティ検査行列 H に対し符号語を

        w = ( x₁  x₂  x₃  x₄  x₅  x₆  x₇ )     ――― (4・6)

とすれば、式(4・1) の検査方程式は

        x₁ h₁ + x₂ h₂ + ... + x₇ h₇ = 0     ――― (4・7)

を表し、H ' の符号語を

        w ' = ( c₆  c₅  c₄  c₃  c₂  c₁  c₀ )     ――― (4・8)

とすれば(添え字に注意)、同じく検査方程式は

        c₆ α⁶ + c₅ α⁵ + ... + c₀ α⁰ = 0     ――― (4・9)

となる。符号語のビット位置を H と H ' の関係と同じく x₁ を c₃ に、x₂ を c₆ に、... と入れ替えてみれば、同一の方程式である。区別する場合、検査行列 H ' をもつ符号を巡回ハミング ( 7 , 4 ) 符号と呼ぶ。

復号器では、受信語

        y ' = ( d₆  d₅  d₄  d₃  d₂  d₁  d₀ )     ――― (4・10)

に対し、式(4・3) のシンドローム

        s = H ' y ' = d₆ α⁶ + d₅ α⁵ + ... + d₀ α⁰     ――― (4・11)

を計算する。列ベクトル α⁶ , ... , α⁰ に d₆ , ... , d₀ を掛け算した和がシンドローム s である。

[2]   H 行列 の 列ベクトル の 発生

列ベクトル α⁰ から α⁶ までを 図 4・1 の 回路 で 発生することができる。これは 3段 の シフトレジスタ回路 となっている。 図において、□ は 1ビット の 記憶素子 (1タイムスロット の 遅延素子) であり、クロックごとに データ は 矢印のほうに 移動する。⊕ は mod2 の 加算回路、すなわち 排他的論理和 exOR を表す。

図 4・1   H ' の列ベクトルを発生する回路

表4・1   シフトレジスタの状態

初期状態として、1 0 0 が入っていたとする。この内容から縦に見て α⁰ である。
最初のシフトでは、いちばん左の 1 が、3番目からフィードバックされてきた 0 と加算され 1 となって2番目に進み、2番目の 0 は3番目に、3番目は1番目にもフィードバックしていく。結果として、シフトレジスタの内容は 0 1 0 となる。同様にして、次のシフトでは 0 0 1 となる。シフトレジスタの内容を時刻順に書けば 表4・1 であり、α⁰ から α⁶ まで順次発生し、7回のシフトで元の状態 α⁰ に戻る。

一般に、m 段のシフトレジスタを使えば、m 行からなる H 行列の列ベクトルが発生できる。図4・1 のように mod2 の加算回路 ⊕ で結線されたフィードバック接続で構成されるシフトレジスタ回路を 線形フィードバックシフトレジスタ (LFSR : Linear Feedback Shift Register) という。LFSR の内容(状態)が初期状態 a₀ から始めれば、a₁ , a₂ , a₃ , ... と変化し、同じく初期状態 b₀ から始めれば、b₁ , b₂ , b₃ , ... になったとする。この LFSR を初期状態 a₀ + b₀ から始めれば、状態は a₁ + b₁ , a₂ + b₂ , a₃ + b₃ , ... のように変化する。このような線形関係が成り立つので、"線形" フィードバックシフトレジスタ と呼ぶ。

[3]   シフトレジスタ による シンドローム の 計算

  図 4・1 の 左端 に 入力部を付けた 図 4・2 の 回路 を 考える。レジスタ の 初期状態 は 0 0 0 とする。
  v₆ = ( 1 0 0 0 0 0 0 ) が クロックごと に １ビットずつ、この回路に入って、最後のビットまで入力し終わったときの状態を考えよう。
  最初 の 1 が 入ると 状態 は 1 0 0 となる。 ⊕ は exOR であり、一方の入力が 0 のときは、他方の入力が そのまま出力に出るので、v₆ の２番目以降 の 0 に対しては 図 4・2 の 回路 は 図 4・1 と 同じ振る舞いをする。
  最後 の 0 が入力された時点では、1 0 0 の状態から 6回シフトした後の状態であり、表 4・1 から 1 0 1 すなわち α⁶ である。同様に v₅ = ( 0 1 0 0 0 0 0 ) が 入力された場合は、2番目の 1 が入った段階で 1 0 0 となる。 残りの 5個の 0 に対して、この レジスタ は 5回シフトするので、最後の状態は 1 1 1 すなわち α⁵ である。
  図 4・2 は LFSR で 線形関係 が 成り立つので、v₆ + v₅ が 入力されれば、最後 の ビット が 入ったとき シフトレジスタ の 状態は α⁶ + α⁵ となる。 したがって、式(4・10) の 受信語 y ' が 1番目のビット d₆ から 最後のビット d₀ まで、この回路に入力されたならば、最後のビットが入ったときの状態は

        d₆ α⁶ + d₅ α⁵ + ... + d₀ α⁰

であり、これは 式(4・11) のシンドローム s である。

図 4・2   シンドローム 計算回路

一般にいうならば、H 行列 の 列ベクトル を 発生する m 段 の LFSR に、図 4・2 と 同じように 入力部 を 設けて 受信語 y を 入力すれば、入力 が 終了したときの レジスタ の状態(内容)が シンドローム s となる。この形の シンドローム計算回路 を もつ 復号器 を、直列型 の 復号器 という。

[4]   シフトレジスタによる符号器

パリティ検査行列 H ' は既約台形正準形であり、式(4・2) の符号語 w は、通報 i に検査ビット列 p

        p = P ' i ^T = [ α⁶ α⁵ α⁴ α³ ] i^T     ――― (４・12)

を付加したものである(3章の 式(3・28) 参照)。通報を

        i = ( i₃ i₂ i₁ i₀ )     ――― (４・13)

とすれば、p は次式であり

        p = i₃ α⁶ + i₂ α⁵ + i₁ α⁴ + i₀ α³     ――― (４・14)

式(4・11) で d₆ = i₃ , d₅ = i₂ , ... , d₃ = i₀ , d₂ = d₁ = d₀ = 0 とおいたものに等しい。同じ 図4・2 の回路に y ' の代わりに

        i ' = ( i₃ i₂ i₁ i₀ 0 0 0 )     ――― (４・15)

の 7ビット を入れれば、LFSR の最後の状態が p となる。したがって、符号器も、受信側のシンドローム計算回路と同じものでよい。工夫するならば、入力部を右端に移動した 図4・3 に、式(4・13) の i を入力してもよい。i₃ = ( 1 0 0 0 ) ならば、最初の 1 が入力された段階で LFSR の状態は 1 1 0 = α³ であり、その後の 3個の 0 で LFSR は 3回シフトするので、最後の状態は α⁶ となる。以下、4・1節 [3]項 と同じ議論で LFSR の最後の状態は p になる。図4・2 で、LFSR のシフト回数は符号長に等しい 7回であり、図4・3 では情報点数に等しい 4回と少なく、図4・3 のほうが計算速度が速い。

図4・3   検査ビット列計算回路

一般に、H 行列の列ベクトルを発生する m 段の LFSR に、図4・3 のように入力部を設けて通報 i を入力すれば、入力が終了したときのレジスタの状態(内容)が検査ビット列 p となる。符号語 w は、i の後ろに p をつなげたものである。この形の符号器を、直列型の符号器という。

[5]   ハミング符号の復号器

巡回ハミング ( 7 , 4 ) 符号の復号器を 図4・4 に示す。図4・2 のシンドローム計算レジスタ R_s , シンドロームパターン検出回路、バッファレジスタ R_b と R₀ , 誤り訂正回路から構成される。シンドロームパターン検出回路は、シンドローム計算レジスタ R_s の内容が 1 0 0 = α⁰ であるときのみ出力 1 を出す。

図4・4   ハミング(7,4)符号の復号器

通信路では符号長7ビット中1か所以下の誤りしか生じないものとして、この回路で誤りが正しく訂正されることを確認してみよう。たとえば、受信語 y ' の d₃ の位置が誤りとする。図4・4 に示す初期状態からスタートし、 y ' の7ビットが入力し終わったときにレジスタ R_s にはシンドローム α³ , R_b , R₀ には、y ' および 0 が入っている。そこからさらにクロックを供給してシフトを続ければ、表4・2 となる。なお、y ' が入力し終わった時刻を 0 とし、それ以降は入力として 0 が入るものとする。

R_s の内容が α⁰ になったときの R₀ 内のビットが誤りであり、R₀ の出力 d₃ はシンドロームパターン検出回路からの出力 1 とともに訂正回路の exOR に入り、誤りが訂正されて出力される。このとき以外はシンドロームパターン検出回路の出力は 0 であり、受信語 y ' の各ビットはそのまま出力される。y ' の 7ビット中任意の 1ビット d_i が誤りの場合、シンドロームは αⁱ であり、さらにシフトして α⁰ となるのに必要なシフト数は 7 - i 回である。したがって、任意の 1ビットの誤りが訂正される。

ここで例に取り上げたハミング符号のように、LFSR を用いて符号器や復号器が構成できる線形符号が巡回符号である。回路が簡単であること、実用的な符号長において符号の効率も比較的高いことから、いちばんよく使われる符号である。