歩き遍路 平成19年春(J1) 記録の準備

Dataパケット用CRC16の
      ハードウエアアルゴリズム

 USBパケット解析のハードウエア化で使えるCRC16のハードウエアアルゴリズムを検討します。

●CRC16のハードウエア化
 CRCは、シフトレジスタと排他的論理和(EXOR)で構成されています。しかしUSBパケット解析を行う場合、フルスピードで12MHz、ハイスピードなら480MHzで処理する必要があるのでそのままハードウエア化はコストがかかります。

 

●CRC16処理の高速化
 高速化ですぐに思いつくのは並列処理です。
 CRC16のの条件は、入力ビット数は制限なし、出力は16ビットです。

 案1:メモリを使う。入力ビット数は制限ないので無限のメモリ容量が必要です。
 案2:CRC16発生の手順を論理式で整理して、論理回路で実現する方式です。

 案1のメモリ方式は無限のメモリ容量が必要なのでこの方式は使えません。
 案2の論理式方式で実現です。CRC5と同様にトライします。

●シフトレジスタとEXORによるCRC16の論理式を手計算
 CRC5の場合最大入力ビットは11ビットなので11ビットのCRCを一度に演算しました。CRC16の演算単位は幾らがよいのでしょうか。データパケットのバイト数は、フルスピードは64バイト、ハイスピードは1024バイトなのでバイト単位の演算が切りが良さそうです。
 16のシフトレジスタと3つのEXORの状態の表を作り、愚直に動作状態を書いていきます。鉛筆で論理式を書くのは転記誤りが多発して纏らない恐れがあるので、表計算に強いExcelのお世話になります。

 左上は16のシフトレジスタと3つのEXORを8回シフトの状態、右は8ビットの入力データの状態です。
 左中は8回シフト後の状態を整理したものです。ビットを順番に並べたり、同じビットを整理しています。同じビットの整理とは、EXORでは”1^1=0””0^0=0”を使っています。
 左下は、00hと00hの2バイト入力を整理した論理式に適用しました。結果はOKです。
 次の表は縮小して見難いのでPDFをここに置きます。




●CRC16手計算の論理式
 CRC16手計算の論理式です。これにビット極性反転とビット位置逆転を加えます。

  C15 = D0^D1^D2^D3^D4^D5^D6^D7^C7^C8^C9^C10^C11^C12^C13^C14^C15
  C14 = C6
  C13 = C5
  C12 = C4
  C11 = C3
  C10 = C2
  C9 = D0^C1^C15
  C8 = D0^D1^C0^C14^C15
  C7 = D1^D2^C13^C14
  C6 = D2^D3^C12^C13
  C5 = D3^D4^C11^C12
  C4 = D4^D5^C10^C11
  C3 = D5^D6^C9^C10
  C2 = D6^D7^C8^C9
  C1 = D0^D1^D2^D3^D4^D5^D6^C9^C10^C11^C12^C13^C14^C15
  C0 = D0^D1^D2^D3^D4^D5^D6^D7^C8^C9^C10^C11^C12^C13^C14^C15

 これなら少しのハードウエアで実現できそうです。安心しました。

●CRC16ハードウエアアルゴリズムの検証
 CRC16ハードウエアアルゴリズムをVisual C# でシュミレートした結果と、パソコンから採取した内容を比べました。入力データが1バイトと2バイトの計算と採取データを目視で確認しましたがOKでした。一部分を写真で示します。





ホームへ戻る