PCI Expressでは、何重にもエラー検出と訂正が行われます。
まず物理層では、8b/10b符号のディスパリティ検査が行われます。
PCI Expressのケーブル上を流れる信号は8b/10b変換という変換が行われた信号です。
この変換を施した信号には、1や0のどちらかの符号が過多にならない、という性質があります。
つまり、エラーなどが起きて、1のほうが不自然に0より多くなると、エラーとなるわけです。
これは物理層チップが調べてくれます。
それから、データリンク層パケットには、16ビットのCRCが付与されます。
また、トランザクション層のパケットには32ビットのCRCが付与されます。
さらに、End-to-Endで使用するためのダイジェストと呼ばれる32ビットのCRCもあります。
このようにいろいろなCRCがあるのですが、参考にしている解説書にはその生成方法が載っていませんでした。
16bitの一般的なCRC生成方法をGoogleで調べてみると、
・16-bit CRC x^16+x^15+x^2+x^0
・CCITT-CRC x^16+x^12+x^5+x^0
などが出てくるのですが、PCI Expressの上の流れるパケットをこれに当てはめてみても、どうしてもうまくいきません。ビットの順序を反転させたり、初期値を変えたりしても駄目です。
32ビットのデータを入力して、16ビットのCRCを作りたいわけです。
具体的には、こんな感じです。
元のデータ => CRC
00000000 => B362
80014011 => 718C
40010010 => FBB9
50010001 => B0DF
60000000 => D892
どうやらCRCの生成方法は、PCI Expressの仕様書を読まないとわからないようです。
というわけで、仕様書をみるとちゃんと書いてありました。
現在開発中のIPコアでは、まずはデータリンク層パケットを自由に送受信したいので、
16ビットCRCを例に生成方法を調べてみることにしました。
仕様書によれば、
・多項式は100B
・初期値はFFFF
・演算結果を全ビット反転(NOTを取る)する。
・Byte0のBit0を一番先に入力する。(ビットリバースされた感覚)
・出力もビットリバースする。
とのことです。
図で書くと、次のようになります。
確かにこの回路をシミュレーションさせてみると、予想どおりの結果が出ました。
しかしこれを実際の回路で使うわけにはいきません。
なぜならば、この回路でCRCを計算すると32クロックを要するからです。
PCI Expressのデータを8bit幅で処理しようとすると、FPGAの動作速度は250MHzになります。
データリンク層パケットは8バイトなので32μ秒で送信されるわけですから、CRCの計算に128μ秒も費やしてはいられません。
ここは、CRCを1クロックで計算する回路が必要になります。
32bitのデータを処理して16bitのCRCを作ればいいわけですから、シフトとXOR演算の操作は32回行われます。
この1回1回の操作を、VHDLでいうところのfunction文で書いてみますと、
function crc_shift ( reg_in : std_logic_vector(15 downto 0) ; bit_in : std_logic)
return std_logic_vector is
variable tmp_out : std_logic_vector(15 downto 0);
begin
if((bit_in xor reg_in(15)) = '1') then
tmp_out := (reg_in(14 downto 0) & "0") xor x"100B";
else
tmp_out := (reg_in(14 downto 0) & "0");
end if;
return tmp_out;
end crc_shift;
となります。
これを32回繰り返すのですが、毎回クロックでシフトすると32クロックかかります。
ここは思い切って、32入力16出力の組み合わせをエイヤッと一発で計算する回路を作りましょう。
論理式で書くと気が遠くなりそうですが、VHDLで書くのは簡単です。
32ビットの入力データ din を処理しようとすると、
process(din)
variable crc_tmp : std_logic_vector(15 downto 0);
begin
crc_tmp := x"FFFF";
U1 : FOR I in 0 to 31 loop
crc_tmp := crc_shift(crc_tmp,din(I));
end loop;
crc <= crc_tmp;
end process;
こんな感じで計算できるわけです。
きっと、論理合成ツールの中ではものすごい論理式が出来上がっていることでしょう。
WebPACKでSpartan3用に論理合成した場合、Translateの際に出る動作速度予測は122MHzとなりました。
Implementすれば125MHzで動きますので、PCI Expressのデータを16ビット幅で処理すれば間に合います。
合成された論理式がどんなのになるのかは、想像がつきませんが、ちょっとだけ手計算してみることにします。
入力されたデータをb(m)....b(m)とします。(mは0から31)
計算途中のデータをx_n(m)で表すことにします。
ここで、nはシフト演算の回数を、mはビット番号を表します。
32回シフト演算を繰り返せばCRCは計算完了ですから、x_32(m)は出力結果を表すことになります。
また、x_0(m)は初期値(=all 1)を表します。
では、計算してみます。なお、+はXORを表します。
x_1(0) = b(0) + x_0(15) = b(0) + 1
x_1(1) = b(0) + x_0(15) + x_0(0) = b(0) + 1 + 1 = b(0)
x_1(2) = x_0(1) = 1
x_1(3) = b(0) + x_0(15) + x_0(2) = b(0) + 1 + 1 = b(0)
x_1(4) = x_0(3) = 1
x_1(5) = x_0(4) = 1
x_1(6) = x_0(5) = 1
x_1(7) = x_0(6) = 1
x_1(8) = x_0(7) = 1
x_1(9) = x_0(8) = 1
x_1(10) = x_0(9) = 1
x_1(11) = x_0(10) = 1
x_1(12) = b(0) + x_0(15) + x_0(11) = b(0) + 1 + 1 = b(0)
x_1(13) = x_0(12) = 1
x_1(14) = x_0(13) = 1
x_1(15) = x_0(14) = 1
1回のシフトとXOR演算を施した後の結果ビットはこのような感じです。
普通の例題に出てくるようなCRC生成回路ならばここで1回クロックを入れるでしょう。
ですが、どんどん次に行きます。
x_2(0) = b(1) + x_1(15) = b(1) + 1
x_2(1) = b(1) + x_1(15) + x_1(0) = b(1) + 1 + b(0) + 1 = b(0)+ b(1)
x_2(2) = x_1(1) = b(0)
x_2(3) = b(1) + x_1(15) + x_1(2) = b(1) + 1 + 1 = b(1)
x_2(4) = x_1(3) = b(0)
x_2(5) = x_1(4) = 1
x_2(6) = x_1(5) = 1
x_2(7) = x_1(6) = 1
x_2(8) = x_1(7) = 1
x_2(9) = x_1(8) = 1
x_2(10) = x_1(9) = 1
x_2(11) = x_1(10) = 1
x_2(12) = b(1) + x_1(15) + x_1(11) = b(1) + 1 + 1 = b(1)
x_2(13) = x_1(12) = b(0)
x_2(14) = x_1(13) = 1
x_2(15) = x_1(14) = 1
2回目の演算を施すと、XORが2回重なって消えるなどのところが出てきます。
演算の線形性を感じます。
次、3回目。
x_3(0) = b(2) + x_2(15) = b(2) + 1
x_3(1) = b(2) + x_2(15) + x_2(0) = b(2) + 1 + b(1) + 1 = b(1)+ b(2)
x_3(2) = x_2(1) = b(0)+ b(1)
x_3(3) = b(2) + x_2(15) + x_2(2) = b(2) + 1 + b(0) = b(0) + b(2)
x_3(4) = x_2(3) = b(1)
x_3(5) = x_2(4) = b(0)
x_3(6) = x_2(5) = 1
x_3(7) = x_2(6) = 1
x_3(8) = x_2(7) = 1
x_3(9) = x_2(8) = 1
x_3(10) = x_2(9) = 1
x_3(11) = x_2(10) = 1
x_3(12) = b(2) + x_2(15) + x_2(11) = b(2) + 1 + 1 = b(2)
x_3(13) = x_2(12) = b(1)
x_3(14) = x_2(13) = b(0)
x_3(15) = x_2(14) = 1
次、4回目。
x_4(0) = b(3) + x_3(15) = b(3) + 1
x_4(1) = b(3) + x_3(15) + x_3(0) = b(3) + 1 + b(2) + 1 = b(2)+ b(3)
x_4(2) = x_3(1) = b(1)+ b(2)
x_4(3) = b(3) + x_3(15) + x_3(2) = b(3) + 1 + b(0) + b(1) = b(0) + b(1) + b(3)
x_4(4) = x_3(3) = b(0) + b(2)
x_4(5) = x_3(4) = b(1)
x_4(6) = x_3(5) = b(0)
x_4(7) = x_3(6) = 1
x_4(8) = x_3(7) = 1
x_4(9) = x_3(8) = 1
x_4(10) = x_3(9) = 1
x_4(11) = x_3(10) = 1
x_4(12) = b(3) + x_3(15) + x_3(11) = b(3) + 1 + 1 = b(3)
x_4(13) = x_3(12) = b(2)
x_4(14) = x_3(13) = b(1)
x_4(15) = x_3(14) = b(0)
4回のシフトで、結果ビットの左端が初期値の'1'ではなくなりました。
次からは計算がややこしくなります。
次、5回目
x_5(0) = b(4) + x_4(15) = b(4) + b(0)
x_5(1) = b(4) + x_4(15) + x_4(0) = b(4) + b(0) + b(3) + 1
x_5(2) = x_4(1) = b(2)+ b(3)
x_5(3) = b(4) + x_4(15) + x_4(2) = b(4) + b(0) + b(1) + b(2)
x_5(4) = x_4(3) = b(0) + b(1) + b(3)
x_5(5) = x_4(4) = b(0) + b(2)
x_5(6) = x_4(5) = b(1)
x_5(7) = x_4(6) = b(0)
x_5(8) = x_4(7) = 1
x_5(9) = x_4(8) = 1
x_5(10) = x_4(9) = 1
x_5(11) = x_4(10) = 1
x_5(12) = b(4) + x_4(15) + x_4(11) = b(4) + b(0) + 1
x_5(13) = x_4(12) = b(3)
x_5(14) = x_4(13) = b(2)
x_5(15) = x_4(14) = b(1)
次、6回目
x_6(0) = b(5) + x_5(15) = b(5) + b(1)
x_6(1) = b(5) + x_5(15) + x_5(0) = b(5) + b(4) + b(0)
x_6(2) = x_5(1) = b(4) + b(0) + b(3) + 1
x_6(3) = b(5) + x_5(15) + x_5(2) = b(5) + b(1) + b(2)+ b(3)
x_6(4) = x_5(3) = b(0) + b(1) + b(2) + b(4)
x_6(5) = x_5(4) = b(0) + b(1) + b(3)
x_6(6) = x_5(5) = b(0) + b(2)
x_6(7) = x_5(6) = b(1)
x_6(8) = x_5(7) = b(0)
x_6(9) = x_5(8) = 1
x_6(10) = x_5(9) = 1
x_6(11) = x_5(10) = 1
x_6(12) = b(5) + x_5(15) + x_5(11) = b(5) + b(1) + 1
x_6(13) = x_5(12) = b(4) + b(0) + 1
x_6(14) = x_5(13) = b(3)
x_6(15) = x_5(14) = b(2)
手計算だとたぶんどこかで間違えるので、このへんにしておきます。
何となく感じがつかめてきました。
このようにやっていくと、いつかそのうち A xor Aのようになって消える項が出てくるのでしょう。
いずれにせよ、CRCの各ビットは、32入力以下のXORゲートの塊で作れるだろうということが想像できます。
最近のコメント