ここでは 2年前期の講義「情報理論」を既に理解しているものとして、回路設計についての説明を行っている。ハミング符号について忘れてしまった者はまずそちらをよく復習しておくこと。
図1 に作成するシステムの概要を示す。4ビットの情報語 d が符号化器に与えられる。符号化器は7ビットの符号語 u を出力する。符号語は通信路や記憶装置を経て復号器に届く。ただし、この途中で符号語の内、1ビットが誤り反転することがある。この誤りは NOT ゲートで再現する。復号器は受信語 v (=u+e, ただし、u は符号語、e は誤りパターン、すなわち誤りのあるビットのみが 1 であり、他のビットが 0 であるベクトル) を入力とする。復号器は v から正しい情報語 d' を求め出力する。
|
|
| 図1. ハミング符号の符号化器と復号器を用いた通信・記憶システム |
まずは符号化器の作成例を示す。以下の行列 G は (7,4)ハミング符号の生成行列の1例である。
符号語 u は情報語 d と 生成行列 G の積 u=dG より得ることができる。つまり、符号化器とは入力と行列 G の積を求める回路である。さて、情報語 d=(d[3], d[2], d[1], d[0]) および符号語 u=(u[6], u[5], …, u[0]) について、式 u=dG および上記生成行列 G より以下の7式が成り立つ。
u[6] = d[3]
u[5] = d[2]
u[4] = d[1]
u[3] = d[0]
u[2] = d[3] ^ d[2] ^ d[1]
u[1] = d[2] ^ d[1] ^ d[0]
u[0] = d[3] ^ d[2] ^ d[0]
以上より、符号化器 HAMMING_ENCODER を以下のように記述することができる。
module HAMMING_ENCODER(D, U);
input [3:0] D; /* 情報語 d */
output [6:0] U; /* 符号語 u */
/* 情報語 d と生成行列 G の積 dG を 符号語 u とする */
assign U[6] = D[3]; /* u[6] = d (1000) (生成行列 G の左から1列目) */
assign U[5] = D[2]; /* u[5] = d (0100) (生成行列 G の左から2列目) */
assign U[4] = D[1]; /* u[4] = d (0010) (生成行列 G の左から3列目) */
assign U[3] = D[0]; /* u[3] = d (0001) (生成行列 G の左から4列目) */
assign U[2] = D[3] ^ D[2] ^ D[1]; /* u[2] = d (1110) (生成行列 G の左から5列目) */
assign U[1] = D[2] ^ D[1] ^ D[0]; /* u[1] = d (0111) (生成行列 G の左から6列目) */
assign U[0] = D[3] ^ D[2] ^ D[0]; /* u[0] = d (1101) (生成行列 G の左から7列目) */
endmodule
|
さて上述の式や verilog-HDL 記述から、符号語 u の6〜3 ビット目が情報語 d と一致していることが分かる。つまり、符号語の下位3ビットを捨てることにより情報語を得ることができる。このように情報語が符号語の一部として出現する符号を組織符号と呼ぶ。
次に復号器を作成する。復号器の概要を図2 に示す。7ビットの受信語 v がシンドローム生成器に与えられる。シンドローム生成器は 3ビットのシンドローム s を出力する。シンドローム s は誤りパターン生成器に与えられる。誤りパターン生成器はシンドロームから発生している誤りを推定し 7ビットの誤りパターン e を出力する。受信語 v と誤りパターン e の和 (排他的論理和) を求めることにより、正しい送信語 u' を求めることができる。送信語 u' のうち、下位3ビットを捨てることにより情報語 d' を得ることができる。
|
| 図2. ハミング符号の復号器 |
復号器 HAMMING_DECODER は以下のように記述することができる。シンドローム生成器 SYNDROME_GENERATOR と誤りパターン生成器 ERROR_PATTERN_GENERATOR は後で作成する。
module HAMMING_DECODER(V, DD);
input [6:0] V; /* 受信語 v */
output [3:0] DD; /* 推定された情報語 d' */
wire [2:0] S; /* シンドローム s */
wire [6:0] E; /* 誤りパターン e */
wire [6:0] UD; /* 推定された送信語 u' */
SYNDROME_GENERATOR SG (.V(V), .S(S)); /* シンドローム生成器 */
ERROR_PATTERN_GENERATOR EPG (.S(S), .E(E)); /* 誤りパターン生成器 */
assign UD = V ^ E;
/* V と E の iビット目 (i=0〜6) について排他的論理和をとり
UD の iビット目とする */
assign DD = UD[6:3];
/* UD の 6〜3ビット目を DD とする */
endmodule
|
次にシンドローム生成器を作成する。シンドローム s は受信語 v と検査行列(の転置行列) HT の積 s=vHT より得ることができる。さて、上記生成行列 G に対応する検査行列 H は以下の通りである。
以下にシンドローム生成器 SYNDROME_GENERATOR の記述例を示す。
module SYNDROME_GENERATOR(V, S);
input [6:0] V; /* 受信語 v */
output [2:0] S; /* シンドローム s*/
/* 受信語 v と検査行列 H の積 vH をシンドローム s とする */
assign S[2] = V[6] ^ V[5] ^ V[4] ^ V[2]; /* s[2] = v (1110100) (検査行列 H の上から1行目) */
assign S[1] = V[5] ^ V[4] ^ V[3] ^ V[1]; /* s[1] = v (0111010) (検査行列 H の上から2行目) */
assign S[0] = V[6] ^ V[5] ^ V[3] ^ V[0]; /* s[0] = v (1101001) (検査行列 H の上から3行目) */
endmodule
|
次に、誤りパターン生成器を作成する。検査行列 H の i 番目の列とシンドローム s が一致したとき、受信語 v の i ビット目に誤りがあると推定し、誤りパターン e の i ビット目を 1 とする。以下に誤りパターン生成器 ERROR_PATTERN_GENERATOR の記述例を示す。
module ERROR_PATTERN_GENERATOR(S, E);
input [2:0] S;
output [6:0] E;
assign E[6] = S[2] & ~S[1] & S[0]; /* シンドローム s が 3'b101 のとき */
assign E[5] = S[2] & S[1] & S[0]; /* シンドローム s が 3'b111 のとき */
assign E[4] = S[2] & S[1] & ~S[0]; /* シンドローム s が 3'b110 のとき */
assign E[3] = ~S[2] & S[1] & S[0]; /* シンドローム s が 3'b011 のとき */
assign E[2] = S[2] & ~S[1] & ~S[0]; /* シンドローム s が 3'b100 のとき */
assign E[1] = ~S[2] & S[1] & ~S[0]; /* シンドローム s が 3'b010 のとき */
assign E[0] = ~S[2] & ~S[1] & S[0]; /* シンドローム s が 3'b001 のとき */
endmodule
|
以下は検証用モジュールの例である。この例では、図1 の例と同様に送信語の5ビット目 u[5] に誤りを発生させている。
`timescale 10ps / 10ps
module TESTBENCH;
reg [3:0] D; /* 情報語 d */
wire [6:0] U; /* 符号語 u */
wire [6:0] V; /* 受信語 v */
wire [3:0] DD; /* 推定された情報語 d' */
HAMMING_ENCODER HE (.D(D), .U(U)); /* 符号化器 */
assign V[6] = U[6];
assign V[5] = ~U[5]; /* 誤りが発生している */
assign V[4] = U[4];
assign V[3] = U[3];
assign V[2] = U[2];
assign V[1] = U[1];
assign V[0] = U[0];
HAMMING_DECODER HD (.V(V), .DD(DD)); /* 復号器 */
initial begin
$dumpfile("HAMMING.vcd");
$dumpvars(1, TESTBENCH);
D <= 4'b0000; #50
D <= 4'b0001; #50
D <= 4'b0010; #50
D <= 4'b0011; #50
D <= 4'b0100; #50
D <= 4'b0101; #50
D <= 4'b0110; #50
D <= 4'b0111; #50
D <= 4'b1000; #50
D <= 4'b1001; #50
D <= 4'b1010; #50
D <= 4'b1011; #50
D <= 4'b1100; #50
D <= 4'b1101; #50
D <= 4'b1110; #50
D <= 4'b1111; #50
$finish;
end
endmodule
|
今までの検証用モジュール中では 1個の検証対象回路 CUT のみ記述してきた。しかし、検証対象回路は検証用モジュール中に複数あっても良い。またその名前も CUT でなくても、なんでもよい。さらに、assign 文を書いても良い。なおこの場合、reg 文で宣言する必要がある入力信号線は initial ブロック内で値を与える信号線のみである。受信語 V は HAMMING_DECODER の入力であるが、その値は assign 文で与えられており、initial ブロック内では与えていない。よって、この場合は wire 文で宣言する。
難波 一輝 (助教・伊藤・北神・難波研究室)
工学部1号棟4階409号室、内線3255、043-290-3255、namba@ieee.org