半導体フロントエンド設計100本ノック、第25問。
今回は32bitデータに対するSEC-DED ECCを実装する。
問題
32bitの入力データにECCを付加し、39bitのcodewordを生成するEncoderと、そのcodewordから元データを復元するDecoderを作る。
構成は、
32-bit data + 6-bit Hamming parity + 1-bit overall parity = 39-bit codeword
とする。
Decoderでは、
- 1bit errorなら検出して訂正する
- 2bit errorなら検出する
- errorがなければそのままdataを返す
こと。
Hamming codeのlogical positionは1-originとし、position 1, 2, 4, 8, 16, 32をparity bitに使う。39bit目はoverall parityとする。
RTLテンプレートは以下。
module ecc_secded32 ( // Encode input logic [31:0] i_enc_data, output logic [38:0] o_codeword, // Decode input logic [38:0] i_codeword, output logic [31:0] o_dec_data, output logic o_single_error, output logic o_double_error ); endmodule
Hamming positionにdataを配置する
まず32bit dataをHamming code上へ配置する。
Hamming codeでは、1-originで見たpositionが2のべき乗になる場所をparity bitとして使う。
position 1 : parity position 2 : parity position 3 : data position 4 : parity position 5 : data ... position 8 : parity ... position 16 : parity ... position 32 : parity
RTLの配列は0-originなので、parity位置は0, 1, 3, 7, 15, 31になる。
そこで一度parity位置を0で埋めた38bitのw_cwrawを作った。
logic [37:0] w_cwraw; assign w_cwraw[0] = 1'b0; assign w_cwraw[1] = 1'b0; assign w_cwraw[2] = i_enc_data[0]; assign w_cwraw[3] = 1'b0; assign w_cwraw[6:4] = i_enc_data[3:1]; assign w_cwraw[7] = 1'b0; assign w_cwraw[14:8] = i_enc_data[10:4]; assign w_cwraw[15] = 1'b0; assign w_cwraw[30:16] = i_enc_data[25:11]; assign w_cwraw[31] = 1'b0; assign w_cwraw[37:32] = i_enc_data[31:26];
parityの所属判定に使うのはdata indexではなく、Hamming code上のposition番号のbitである。
parity bitを計算する
各parity bitは、Hamming positionの対応するbitが1になっているpositionをXORする。
RTLでは、配列indexから1-origin positionへ変換してから判定する。
logic [5:0] w_parity;
always_comb begin
w_parity = '0;
for (int idx = 0; idx < 38; idx++) begin
int pos;
pos = idx + 1;
for (int p = 0; p < 6; p++) begin
if (pos[p]) begin
w_parity[p] ^= w_cwraw[idx];
end
end
end
end
w_cwrawではparity位置を0にしているので、そのposition自身をXOR対象に含めても結果には影響しない。
計算したparityを元の位置へ戻す。
assign o_codeword[0] = w_parity[0]; assign o_codeword[1] = w_parity[1]; assign o_codeword[2] = i_enc_data[0]; assign o_codeword[3] = w_parity[2]; assign o_codeword[6:4] = i_enc_data[3:1]; assign o_codeword[7] = w_parity[3]; assign o_codeword[14:8] = i_enc_data[10:4]; assign o_codeword[15] = w_parity[4]; assign o_codeword[30:16] = i_enc_data[25:11]; assign o_codeword[31] = w_parity[5]; assign o_codeword[37:32] = i_enc_data[31:26];
最後にoverall parityを追加する。
assign o_codeword[38] = ^o_codeword[37:0];
今回はeven parityなので、39bit全体のXORが0になるようにしている。
Decodeではsyndromeを作る
Decode側も同じparity groupingを使ってcheckする。
今回は受信したparity bit自身も含めてXORする。
logic [5:0] w_syndrome;
always_comb begin
w_syndrome = '0;
for (int idx = 0; idx < 38; idx++) begin
int dec_pos;
dec_pos = idx + 1;
for (int p = 0; p < 6; p++) begin
if (dec_pos[p]) begin
w_syndrome[p] ^= i_codeword[idx];
end
end
end
end
errorがなければw_syndrome=0になる。
Hamming領域で1bit errorが起きた場合は、w_syndromeがそのHamming positionを示す。
overall parityと組み合わせる
overall parityも受信した39bit全体のXORで確認する。
logic w_overall_error; assign w_overall_error = ^i_codeword;
syndromeとoverall_errorの組み合わせは以下になる。
syndrome = 0, overall = 0
→ errorなし
syndrome != 0, overall = 1
→ Hamming領域の1bit error
syndrome = 0, overall = 1
→ overall parity bit自身の1bit error
syndrome != 0, overall = 0
→ double-bit error
したがって、
assign o_single_error = w_overall_error; assign o_double_error = (|w_syndrome) && !w_overall_error;
とした。
single-bit errorを訂正する
訂正は32bit dataへ直接かけるのではなく、38bitのHamming codeword上で行う。
syndromeが示すのはdata indexではなくHamming positionだからである。
logic [37:0] w_corrected_codeword;
always_comb begin
w_corrected_codeword = i_codeword[37:0];
if (w_overall_error &&
(|w_syndrome) &&
(w_syndrome <= 6'd38)) begin
w_corrected_codeword[w_syndrome-1]
= ~w_corrected_codeword[w_syndrome-1];
end
end
overall_error=1かつsyndrome!=0のときだけ訂正する。
double-bit errorではsyndrome!=0になることがあるため、syndromeだけを見て反転すると誤訂正してしまう。
overall parity bitだけが壊れた場合はsyndrome=0なので、data側はそのままでよい。
最後に、訂正済みcodewordからdataだけを取り出す。
assign o_dec_data = {
w_corrected_codeword[37:32],
w_corrected_codeword[30:16],
w_corrected_codeword[14:8],
w_corrected_codeword[6:4],
w_corrected_codeword[2]
};
RTL
最終的には以下のようになった。
module ecc_secded32 (
input logic [31:0] i_enc_data,
output logic [38:0] o_codeword,
input logic [38:0] i_codeword,
output logic [31:0] o_dec_data,
output logic o_single_error,
output logic o_double_error
);
logic [37:0] w_cwraw;
assign w_cwraw[0] = 1'b0;
assign w_cwraw[1] = 1'b0;
assign w_cwraw[2] = i_enc_data[0];
assign w_cwraw[3] = 1'b0;
assign w_cwraw[6:4] = i_enc_data[3:1];
assign w_cwraw[7] = 1'b0;
assign w_cwraw[14:8] = i_enc_data[10:4];
assign w_cwraw[15] = 1'b0;
assign w_cwraw[30:16] = i_enc_data[25:11];
assign w_cwraw[31] = 1'b0;
assign w_cwraw[37:32] = i_enc_data[31:26];
logic [5:0] w_parity;
always_comb begin
w_parity = '0;
for (int idx = 0; idx < 38; idx++) begin
int pos;
pos = idx + 1;
for (int p = 0; p < 6; p++) begin
if (pos[p])
w_parity[p] ^= w_cwraw[idx];
end
end
end
assign o_codeword[0] = w_parity[0];
assign o_codeword[1] = w_parity[1];
assign o_codeword[2] = i_enc_data[0];
assign o_codeword[3] = w_parity[2];
assign o_codeword[6:4] = i_enc_data[3:1];
assign o_codeword[7] = w_parity[3];
assign o_codeword[14:8] = i_enc_data[10:4];
assign o_codeword[15] = w_parity[4];
assign o_codeword[30:16] = i_enc_data[25:11];
assign o_codeword[31] = w_parity[5];
assign o_codeword[37:32] = i_enc_data[31:26];
assign o_codeword[38] = ^o_codeword[37:0];
logic [5:0] w_syndrome;
always_comb begin
w_syndrome = '0;
for (int idx = 0; idx < 38; idx++) begin
int dec_pos;
dec_pos = idx + 1;
for (int p = 0; p < 6; p++) begin
if (dec_pos[p])
w_syndrome[p] ^= i_codeword[idx];
end
end
end
logic w_overall_error;
assign w_overall_error = ^i_codeword;
assign o_single_error = w_overall_error;
assign o_double_error = (|w_syndrome) && !w_overall_error;
logic [37:0] w_corrected_codeword;
always_comb begin
w_corrected_codeword = i_codeword[37:0];
if (w_overall_error &&
(|w_syndrome) &&
(w_syndrome <= 6'd38)) begin
w_corrected_codeword[w_syndrome-1]
= ~w_corrected_codeword[w_syndrome-1];
end
end
assign o_dec_data = {
w_corrected_codeword[37:32],
w_corrected_codeword[30:16],
w_corrected_codeword[14:8],
w_corrected_codeword[6:4],
w_corrected_codeword[2]
};
endmodule