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

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

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

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

 

●CRC5処理の高速化
 高速化ですぐに思いつくのは並列処理です。
 CRC5のの条件は、入力は11ビット、出力は5ビットです。

 案1:メモリを使う。入力の11ビットをアドレスに入れてデータ出力の5ビットを得る方式です。
 案2:CRC5発生の手順を論理式で整理して、論理回路で実現する方式です。

 案1のメモリ方式は2Kバイトのメモリで実現できますが、論理式方式は実現できるか不明です!

 「はじめ」で書いた「ここでは、己の気の趣くままに失敗を恐れず、己の無知 無能 を省みずエレキの実験をしてその内容を主に記録していきたいと思っています。」を思い出し、論理式方式を検討きます。ダメだったら又考えたらイイや!

●シフトレジスタとEXORによるCRC5の論理式を手計算
 CRC5の値を得るには、5つのシフトレジスタと2つのEXOR動作を11回する必要があります。
 5つのシフトレジスタと2つのEXORの状態の表を作り、愚直に動作状態を書いていきます。
 しかし、延々と鉛筆で論理式を書くのは転記誤りが多発して纏らない恐れがあるので、表計算に強いExcelのお世話になります。表計算に強いExcelでもマクロを使って一発で作成とはいかず、セルからセルの転記は手作業です。

 左上は5つのシフトレジスタと2つのEXORを11回シフトの状態、右は11ビットの入力データの状態です。
 左下は11回シフト後の状態を整理したものです。ビットを順番に並べたり、同じビットを整理しています。同じビットの整理とは、EXORでは”1^1=0””0^0=0”を使っています。
 次の表は縮小して見難いのでPDFをここに置きます。




●CRC5手計算の論理式
 CRC5手計算の論理式です。

  C4 = C2^D2^C4^D0^D5^C4^D0^C1^D3^D8^C4^D0^C1^D3^C3^D1^D6
  C3 = C4^D0^C1^D3^C3^D1^D6^C3^D1^C0^D4^D9^C3^D1^C0^D4^C2^D2^D7
  C2 = C3^D1^C0^D4^C2^D2^D7^C2^D2^C4^D0^D5^D10^C2^D2^C4^D0^D5^C4^D0^C1^D3^D8
  C1 = C4^D0^C1^D3^C3^D1^D6^C3^D1^C0^D4^D9
  C0 = C3^D1^C0^D4^C2^D2^D7^C2^D2^C4^D0^D5^D10

 これを順番に並べて、同じビット番号を整理します。
 整理方法は、EXOR演算の ”1^1=0””0^0=0”を使ってします。

  C4 = D0^D1^D2^D5^D6^D8^C2^C3^C4
  C3 = D0^D1^D2^D3^D6^D7^D9^C1^C2^C3^C4
  C2 = D0^D1^D2^D3^D4^D7^D8^D10^C0^C1^C2^C3^C4
  C1 = D0^D3^D4^D6^D9^C0^C1^C4
  C0 = D0^D1^D4^D5^D7^D10^C0^C3^C4

 これにビット極性反転とビット位置逆転を加えても少しのハードウエアで実現できそうです。安心しました。

●CRC5ハードウエアアルゴリズムの検証
 CRC5ハードウエアアルゴリズムをVisual C# でシュミレートして確認しましたがOKでした。2000行以上有るので一部分だけの写真を示します。





ホームへ戻る