FPGA開発日記

カテゴリ別記事インデックス https://msyksphinz.github.io/github_pages , English Version https://fpgadevdiary.hatenadiary.com/

半導体フロントエンド設計100本ノック (25) SEC-DED ECC

半導体フロントエンド設計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