2.2   符号 と 符号化

  本節では、符号 の 分類 および 線形符号 の 性質 について 簡単に説明し、その 生成方法 を 学ぶ。 また、もっとも 単純な 設計符号である 単一パリティ検査符号 についても 触れる。

2.2.1   ブロック符号 と 非ブロック符号

  図 2.6 に 示すように、情報源符号化 された ビット系列 を 一定長 に 区切った それぞれを 情報ブロック といい、ブロックごとに 通信路符号化 したものを 符号ブロック という。 また、符号ブロックの集合を ブロック符号 という。
グロック符号 において、各ブロック を 符号語 (codeword), 符号語 の 長さ (ビットなどの個数) を 符号長 (code length) という。 一般に、符号語 を 元 とする 集合 を 符号 (code) という。 (図 2.7)

図 2.6   符号長 10 の 符号語 と 受信語 の 例

図 2.7   符号 と 符号語

なお、2元 { 0, 1 } から 構成される 符号 を 2元符号 (binary code) といい、q 進数 のような、q 個 の
元 { α₁, α₂, …, α_q } から 構成される 符号 を q 元符号 という。 符号語 の 系列 を 通信路 を 介して 送受信 するとき、受信系列 の 各ブロック を 受信語 (received code) という。

  また、ブロック符号 以外の 符号 を 非ブロック符号 (non block code) といい、その代表的なものに 第7章 で述べる 畳込み符号 (convolutional code) がある。 畳込み符号 でも 形式的に ブロック を 用いて 符号化 が 行われる。

  以下では、実際の 情報伝送で よく用いられる 2元符号 の 場合を考える。 符号長 n の 符号語 は、符号語 の 各ビット w_i を 成分とする n 次元ベクトル と みなすことができる。 たとえば、符号長 5 の 符号語 w₁ w₂ w₃ w₄ w₅ は 5次元ベクトル と みなして、w = (w₁, w₂, w₃, w₄, w₅)、または、簡単に w = w₁ w₂ w₃ w₄ w₅ と 表す。

  情報ブロックが、k 個 の ビット から なる 場合を 考えてみよう。 通信路符号化 によって 符号長 n の 符号語 が 生成されるとき (図 2.6 参照)、k 個 の ビット を 情報ビット系列 といい、情報ブロック に 付加される n - k 個 の ビット を パリティ検査ビット系列 という。 このような 構成 をもつ ブロック符号 を (n, k) 符号 といい、比 R = k / n を 符号化率 (coding rate) という。 なお、情報ビット系列、符号語 を、それぞれ 情報ベクトル (information vector)、符号ベクトル (code vector) とも いう。

2.2.2   単一パリティ検査符号

  単一パリティ検査符号 (single parity check code) とは、1個 の 誤り を 検出する もっとも 単純な ブロック符号 である。 これは、一定長 の 情報ビット系列 に 1ビット を 付加したものを 符号語 とする 符号 である。 この 付加される ビット を パリティ検査ビット (parity check bit) といい、符号語 に 含まれる 1 の 数 が 偶数個 となるように ビット を 末尾に付加する。 たとえば、3ビット の 情報ビット系列 であれば、000, 001, 010, 100, 011, 101, 110, 111 の 8通り があり、パリティ検査ビット を 付加 すると 表 2.1 のような 単一パリティ検査符号 を 得る。

  このような パリティ検査ビット を 付加 することで、受信語 に 含まれる 1 の 数 が 奇数個 であれば 誤り があることがわかる。 ただし、この符号では 受信語 の どの箇所に 誤り があるのか わからないので、誤り の 訂正 は できない。

  一般に、符号長 n = k + 1 の 単一パリティ検査符号 では、情報ビット系列 を w₁ w₂ … w_k とすると、符号語 は

        w₁ w₂ … w_k c     ――― (2.1)

で 与えられる。 ただし、パリティ検査ビット c は

        c = w₁ + w₂ + … + w_k     ――― (2.2)

で ある。 ここで、記号 ＋ は 2 を 法 とする 加法 で、これは 排他的論理和 とも よばれ、

        0 + 0 = 0,   0 + 1 = 1,   1 + 0 = 1,   1 + 1 = 0     ――― (2.3)

のように 定義 される (3.1 節 参照)。 このように、単一パリティ検査符号 は (k + 1, k) 符号 であり、奇数個 の 誤り を 検出することができる。

2.2.3   線形符号 と 生成行列

  符号 C の 任意 の 符号語 w₁, w₂ に対して、和 w₁ + w₂ も また C の 符号語 であるとき、C を 線形符号 (linear code) という (図 2.8)。 このとき、符号 C は 和 に関して 閉じている という。 実際に 工学で 用いられている 符号 は、ほとんど が 線形符号 である。

図 2.8   線形符号 C

  (n, k) 線形符号 では、符号化 により k 個 の 情報ビット (情報ベクトル) は 長さ n の 符号語 (符号ベクトル) に 変換される。 この変換は、行列 によって 表される。 いま、情報ベクトル および 符号ベクトル を、それぞれ α = (α₁, α₂, …, α_k), w = (w₁, w₂, …, w_n) と すると、行列 G を k × n 行列 として、(n, k) 線形符号 は

        w = α G     ――― (2.4)

により生成される。 この 行列 G を 生成行列 (generator matrix) といい、成分表示 は

となる。 このような 符号化 は、k 次元 の 情報ベクトル から n 次元 の 符号ベクトル への 線形写像 である (詳しくは、線形代数学の本を参照)。

例題 2.1

単一パリティ検査符号 は 線形符号 であることを 示せ。

解答

符号長 k + 1 の 単一パリティ検査符号 を C とする。 C の 任意 の 二つの 符号語 w₁, w₂ を

        w₁ = (x₁, x₂, …, x_k, c₁),     w₂ = (y₁, y₂, …, y_k, c₂)     ――― (2.6)

と おく。 ただし、c₁ = x₁ + x₂ + … + x_k,   c₂ = y₁ + y₂ + … + y_k である。

このとき

        w₁ + w₂ = ( x₁ + y₁,   x₂ + y₂,   …,   x_k + y_k,   c₁ + c₂ )     ――― (2.7)

であるが、

        (x₁ + y₁) + (x₂ + y₂) + … + (x_k + y_k) = c₁ + c₂     ――― (2.8)

と なり、c₁ + c₂ は w₁ + w₂ の パリティ検査ビット である。 よって、C は 線形符号 である。 ◆

例題 2.2

符号長 5 の 線形符号 C の 生成行列 を

と する。 G によって生成される 線形符号 C を 求めよ。

解答

符号長 n = k + 1 = 5 より k = 4 であるから、情報ベクトル を α = ( a₁, a₂, a₃ ) ( a₁, a₂, a₃ ∈ { 0, 1 } ) とおく、情報ベクトル α と G の 積 より、

        C = { ( a₁, a₂, a₃ ) G ｜a₁, a₂, a₃ ∈ { 0, 1 } }
          = { ( a₁ + a₃,  a₁ + a₂,  a₂ + a₃,  a₃,  a₂ ) | a₁, a₂, a₃∈ { 0, 1 } }     ――― (2.9)

と なる。 ここで、たとえば a₁ = 1, a₂ = 0, a₃ = 1 を 代入すると、C の 元 は ( 0, 1, 1, 1, 0 ) となる。 これを "01110" で表す。 a₁, a₂, a₃ の おのおのに 0, 1 を 代入すると、線形符号

        C = { 00000, 11000, 01101, 10110, 10101, 01110, 11011, 00011 }     ――― (2.10)

を 得る。 この符号 C は k = 3, n = 5 であるから、(5, 3) 線形符号 である。 ◆

例題 2.3

符号長 5 の 単一パリティ検査符号 C の 生成行列 G を 導き、C の 符号語 すべて 求めよ。

解答

符号長 n = k + 1 = 5 より k = 4 であるから、情報ベクトル を α = (a₁, a₂, a₃, a₄) とおくと、パリティ検査ビット C は、

  c = a₁ + a₂ + a₃ + a₄   ――― (2.11)

である。 このとき、符号語 w は、

  w = (a₁, a₂, a₃, a₄, c)

    = (a₁, a₂, a₃, a₄, a₁ + a₂ + a₃ + a₄)

    = (a₁, a₂, a₃, a₄, 0) + (0, 0, 0, 0, a₁ + a₂ + a₃ + a₄)

と 表される。 これにより、生成行列 は、

となる。 また、w = (a₁, a₂, a₃, a₄, c) の 情報ビット系列 a₁ a₂ a₃ a₄ の おのおの に 0, 1 を 代入すると、符号長 5 の 単一パリティ検査符号

    C = { 00000, 10001, 01001, 00101, 00011, 11000, 10100, 10010
            01100, 01010, 00110, 11101, 11011, 10111, 01111, 11110 }   ―― (2.14)

を得る。

2.2.4   組織符号 と その生成

  図 2.9 のように、情報ビット系列 と パリティ検査ビット系列 の 位置 が 明確に分かれている 符号 を、組織符号 (systematic code) という。 符号長 と 情報ビット数 を 明示して (n, k) 組織符号 ともいう。

図 2.9   (n, k) 組織符号 の 符号

  例題 2.2 のように、単に G を 乗じる 符号化 では、情報ビット系列 α = a₁ a₂ a₃ は ばらばら に なって 符号化 され、組織符号 にならない。 この場合、受信語 から 情報ビット系列 を 取り出すには 別の処理が必要となり、効率的 でない。

  そこで、ここでは、行列 の 既約標準形 というものを 利用する 組織符号 の 生成方法について 述べる。

  図 2.10 のように、k × n (k < n) の 生成符号 G の 左側 の k × k 行列 の 階数 が k の とき、行基本操作 (1.5節参照) によって、G を つぎの 形 に 変形 することができる。

        G₀ = (I_k P)     ――― (2.15)

図 2.10   (n, k) 既約標準形 への 変形

ここで、I_k は k 次 の 単位行列 である。 このような 生成行列 G₀ の 形 を 既約標準形 という。 もし、G の 左側 の k × k 行列 の 階数 が k より 小さければ、G の 列ベクトル の 適当な 入れ換え によって 階数 を k にしておく。

  生成行列 が 既約標準形 G₀ の場合、情報ベクトル を α = (a₁, a₂, …, a_k) とすると、

        α G₀ = α (I_k P) = (α  α P)     ――― (2.16)

のように 符号化 される。 この 符号語 (α, α P) は、情報ビット系列 α が まとまっているので 組織符号 に なっている。 (図 2.11)

図 2.11   組織符号 の 生成

例題 2.4

(6, 4) 線形符号 の 生成行列 を

とする。

(1) 既約標準形 G₀ を 求めよ。

(2) 情報ベクトル α = (a₁, a₂, a₃, a₄) を G₀ によって 符号化 せよ。

解答

(1) そのまま 行基本操作 を 行うと G は

と なり、左側 4 × 4 行列 の 階数 は 3 であり 単位行列 にできない。 そこで G の 第4列 と 第5列 を 入れ換えた行列

について 行基本操作 を 行うと、

と なる。 これより、G の 既約標準形

が 得られる。

(2) 情報ベクトル α = (a₁, a₂, a₃, a₄) と G₀ の 積 より、

          = (a₁, a₂, a₃, a₄, a₂+a₃, a₁)     ――― (2.21)

と なる。 式(2.21) は 左側 4ビット が 情報ビット系列 に 一致し、組織符号 に なっている。 ◆

2.2.5   パリティ検査行列

  (n, k) 線形符号 C の 生成行列 G は k × n 行列 であり、符号語 は w = α G によって 生成される。 いま、(n - k) × n 行列 H があり、

        G H ^T = Ο   (Ο は k × (n - k) の 0 行列)     ――― (2.22)

を 満たすとする。 このとき、式(2.22) の 両辺に 左から 情報ベクトル α を かけると、

        w H ^T = 0     ――― (2.23)

と なる。 この式を パリティ検査方程式 (parity chech equation) といい、(n - k) × n 行列 H を パリティ検査行列 (parity check matrix) という。 式(2.23) から わかるように、H の 列数 は 符号長 に 等しい。 パリティ検査行列 H が 与えられているとき、式(2.23) を 満たす 符号語 w の 全体は (n, k) 線形符号 を つくる。

  G が 既約標準形 (I_k P) の場合は、式(2.22) を満たす H は ( -P ^T  I_n-k ) と なる (図 2.12)。
実際、このとき、

と なる。

(a)   G の 既約標準形		(b)   H の 既約標準形
図 2.12   G と H の 既約標準形

例題 2.5

（7, 3) 線形符号 の 生成行列 を

と する。 パリティ検査行列 H を 求めよ。

解答

と なる     ◆