マキシムの1-WireおよびiButton製品に用いる巡回冗長検査(CRC)の理解と用法

2004年09月27日

155.00K

要約

iButton^®デバイスを含むすべての1-Wire^®デバイスには、読取り専用メモリ(ROM)内に8バイトの一意の登録番号が含まれています。この登録番号は、1-Wireバス上で一意のネットワークアドレスとして使用されます。データ通信の完全性を保証するため、各登録番号の1バイトが1-Wire CRCバイトとして使用されています。このアプリケーションノートでは、この8ビットの1-Wire CRCの計算方法について説明します。また、デバイスのメモリ内に保存されているレコードの検証に使用する16ビットCRCについても説明します。1-Wire CRCとCRC-16はどちらも、選択された1-Wireデバイスのハードウェア内で生成され、データを検証します。

はじめに

マキシムのiButton製品は、1-Wireプロトコルと呼ばれる特別なコマンドシーケンスに従って、単線を使ってすべての通信を行うデバイスファミリです。各デバイスの重要な特長は、製造時に各部品に書き込まれた8バイトの一意のROMコードです。この8バイトのコードの構成を図1に示します。最下位バイトには、iButton製品の種類を特定するファミリコードが格納されます。たとえば、DS1990Aは01 (16進数)のファミリコードを持ち、DS1922Lは41 (16進数)のファミリコードを持ちます。同種または異種のファミリの複数デバイスが、同じ1-Wireバスに同時に存在することが可能であるため、1-Wireバス上に配置された各デバイスに正しくアクセスする方法をホストが決定することが重要です。ファミリコードが、この情報を提供します。次の6バイトは、同じファミリコードに属する複数のデバイスを区別できるようにするための一意のシリアル番号です。この一意のシリアル番号は、1-Wireバス上の各デバイスの｢アドレス｣と考えることができます。1-Wireデバイスの集合全体にホストを加えたものが、一種の小規模なローカルエリアネットワーク(MicroLAN)を形成し、これらがすべて共通の単線で通信します。各デバイスのROMコード内の最上位バイトには、巡回冗長検査(CRC)の値が格納されており、これはその部分よりも前にある7バイトのデータに基づいたものです。ホストシステムがデバイスと通信を開始するとき、LSBを先頭として8バイトのROMを読み取ります。ホストによって計算されたCRCがROMデータのバイト7に含まれるCRCと一致すれば、その通信は正しいと考えることができます。一致しない場合はエラーが発生しており、ROMコードを再び読み取る必要があります。

図1. 1-Wire CRCを使用したiButtonのシステム構成

iButton製品の中には、適切なコマンドを用いてホストシステムがアクセス可能なROMの8バイトに加えて、最大8kBのランダムアクセスメモリ(RAM)を持つものもあります。iButtonデバイスがCRCハードウェアを搭載していない場合でも、ホストがROMコードのCRC値を計算することが可能であれば、CRCを使用してデバイスのRAM部分にデータを保存したり取り出したりする方法を開発することも可能です。データは通常の方法でデバイスに書き込むことができます。次に、ホストによって計算されたCRC値が付加され、データとともに保存されます。このデータをiButtonデバイスから取り出すときは、逆のプロセスとなります。ホストは、データバイト用に算出されたCRC値と、そのデータのCRCとしてメモリ内に保存された値とを比較します。2つの値が同じであれば、iButtonデバイスから読み取ったデータは正しいと考えることができます。CRCの能力を活用して1-Wireバス上のシリアル通信を検証するためには、CRCがどのようなものか、またその働きについて理解しておく必要があります。また、ハードウェアまたはソフトウェア実装には、ホストによるCRC値の計算を実際に行う必要があります。

背景

シリアルデータは、さまざまな方法でエラーチェックを行うことができます。一般的な方法の1つとしては、チェックする各パケットにビットを追加して、エラーが発生したかどうかを表示することです。たとえば、8ビットのASCII文字のパケットにおいて、ASCII文字に追加ビットを付加し、文字にエラーが含まれるかどうかが分かるようにします。11010001というビット列からなるデータについて考えてみましょう。1であるビットの総数が常に奇数になるように9番目のビットを付加することにします。すると1が付加され、データパケットは111010001となります。下線を引いた文字は、9ビットのパケット全体で奇数ビットとなるために必要なパリティビットの値を示しています。受け取ったデータが111010001であれば、情報は正確であると見なされます。一方、受け取ったデータが111010101である場合、つまり、左から7番目のビットが誤って受け取られた場合、1の総数は奇数とはならず、エラー状態が検出され、適切な処置が講じられます。この種の方式は、奇数パリティと呼ばれています。同様に、1の総数が常に偶数となるような選択も可能で、これは偶数パリティと呼ばれます。ただし、この方式は、奇数のビットエラーを検出する場合に限られます。上記の例では、データが壊れて111011101となった場合、つまり、左から6番目と7番目のビットが誤りである場合、パリティチェックでは正しいものと見なされますが、偶数または奇数パリティのいずれが使用されていても、エラーは検出されないままです。

説明

マキシムの1-Wire CRC

最小限のハードウェアを用いてシリアルデータストリーム内のエラーを発見する最も有効なエラー検出方式は、CRCです。ここでは、マキシムの製品で使用されるCRC機能の動作と特性について説明します。ただし、命令文や記述文を証明する数学的な詳細は省かれています。CRCの特性の背景にある数学的な概念については、参考資料に詳しく説明されています。CRCは、図2に示すように、実際にはハードウェアで構築される機能(一般的に、フィードバックを備えたシフトレジスタ構成として表現される)と考えると、最も容易に理解することができます。あるいは、CRCは、各項にバイナリ係数を持つ、ダミー変数Xによる多項式と見なされることもあります。係数は、シフトレジスタ実装の中に示されるフィードバックパスに直接対応します。ハードウェアで記述した場合のシフトレジスタの段数、すなわち多項式内に存在する最高次の係数が、算出されるCRC値の大きさを示します。デジタルデータ通信において一般的に使用されるCRCコードは、CRC-16およびCRC-CCITTで、それぞれが16ビットのCRC値を計算します。マキシムの1-Wire CRCの大きさは8ビットで、これを使用して各1-Wire製品に書き込まれた64ビットのROMコードをチェックします。このROMコードは、最下位バイトに書き込まれた8ビットのファミリコード、次の6バイトに書き込まれた48ビットのシリアル番号、および最上位バイトに書き込まれたCRC値(先行するROMの56ビットを用いて計算される)で構成されています。図2において排他的論理和ゲートによって示されたフィードバックパスの配置、すなわち多項式内の係数の存在が、CRCの特性とアルゴリズムの能力(データ内の特定タイプのエラーを見つける)を決定します。1-Wire CRCの場合、検出可能なエラーのタイプは以下のとおりです。

64ビット数値内の任意の場所にある奇数個のエラーのすべて
64ビット数値内の任意の場所にあるダブルビットエラーのすべて
8ビットの｢ウィンドウ｣内に含まれる任意のエラー群(1～8ビットの誤り)
これより大きなエラー群のほとんど

入力データは、図2に示されるシフトレジスタの第8段の出力と排他的論理和が取られます。シフトレジスタは、数学的には、除算回路と考えることができます。入力データは被除数で、フィードバックを備えたシフトレジスタが除数として働きます。得られた商は切り捨てられ、余りが、特定ストリームの入力データのCRC値となり、最後のデータビットがシフトインされた後にこの値がシフトレジスタ内に残ります。シフトレジスタの実装から明らかなように、最終結果(CRC値)は、非常に複雑な方法で、提示されたビットの履歴に依存しているということです。したがって、非常にまれな組合せのエラーが起こらない限り、この方法による検出から免れることはできません。

図2. マキシム1-Wireの8ビットCRC

例2は、各データビットが入力された後のCRC値を計算しています。シフトレジスタ回路は、計算の開始と同時に常に0にリセットされます。計算は64ビットのROMのLSBから始まり、それはこの例では、02 (16進数)のファミリコードです。56ビットデータのすべて(シリアル番号 + ファミリコード)が入力された後、シフトレジスタ内に含まれる値はA2 (16進数)となり、これが、この入力ストリームの1-Wire CRC値となります。この計算されたCRC値(この例ではA2 (16進数))が、次の8ビットデータのシフトレジスタへの入力として使用されると、64ビットの全データが入力された後のシフトレジスタにおける最終結果は、すべて0になるはずです。この特性は、1-Wire CRCアルゴリズムに常に当てはまります。シフトレジスタ内に発生するいずれの8ビット値も、入力ストリーム内の次の8ビットとして使用されるので、8番目のデータビットがシフトインされた後にシフトレジスタ内に表れる結果は常に00 (16進数)となります。この理由は、シフトレジスタの第8段の内容が、入ってくるデータビットに常に等しくなるからです。こうして、フィードバックを制御するEXORゲートの出力とシフトレジスタの第1段の次の状態値は常にロジック0となります。これによって、シフトレジスタは、各データビットの入力に伴って単純に0が左から右にシフトされ、最終的に8番目のビット以降すべてのレジスタが0で満たされます。マキシムの1-Wireの64ビットROMの構造は、この特性を用いて、ROMの読取りに使用するデバイスのハードウェア設計を簡素化しています。ホスト内のシフトレジスタが消去された後、CRC値を含むROMの64ビットが読み取られます。正しい読取りが行われると、シフトレジスタは再びすべて0となり、検出しやすい状態になります。0でない値がシフトレジスタ内に残ると、読取り動作を繰り返す必要があります。

ここまでは、CRCプロセスをハードウェアで表現することについて議論を集中してきましたが、当然、ハードウェア手法に匹敵するソフトウェアソリューションも存在し、1-Wire CRCの値を算出する別の手段になります。この方法をコード化する例を表1に示します。Aレジスタと定数18 (16進数)とのXRL (排他的論理和)は、図2に示す第4段と第5段の後に置かれた1-Wire CRC内のEXORフィードバックゲートの存在に起因するものであることがわかります。また別のソフトウェアソリューションとしては、CRCレジスタ内に現在保存されている任意の8ビットの値と新しいデータの任意の8ビットパターンに対して直接アクセスできるルックアップテーブルを構築するだけというものもあります。たとえば、CRCレジスタの現在の値が00 (16進数)という単純なケースでは、入力バイトに対して256種類のビットの組み合わせに対する値を求めてこれを行列に格納することができます。この行列のインデックスが入力バイトの値(すなわちインデックスI = 0～255)に等しくなります。CRCレジスタの現在の値が00 (16進数)でない場合、現在のCRC値および任意の入力バイトに対するルックアップテーブルの値は単純化されたケースの場合と同じとなりますが、テーブルへのインデックスの計算は、下の式になります。

新しいCRC = Table [I] (I = 0～255)
ここで、I = (現在のCRC) EXOR (入力バイト)

現在のCRCレジスタ値が00 (16進数)のケースの場合には、この式は単純なケースになります。この2番目の手法は、前の例のようにビット指向のコマンドではなくバイト単位による演算が可能であるため、計算にかかる時間を短縮することができます。ただし、トレードオフとしてメモリ容量が犠牲となります。これはプログラムコード以外に実質的にメモリが不要な最初の例に比べ、ルックアップテーブルを保存する必要があるため256バイトを消費するからです。この種のコードの例を例3に示します。表1は、参照テーブルの手法を用いて前の例を繰り返して示したものです。CRC値の計算に使用されるコードをデバッグするためには、1-Wire CRCの2つの特性が役立ちます。1つ目の特性は、ハードウェアによる実装の場合にすでに述べた通りです。すなわち、CRCレジスタの現在の値が次のバイトのデータとして使用される場合、結果として得られるCRC値は、常に00 (16進数)になるというものです(前述の説明を参照)。コードの正しい動作を確認するために使用可能な2つ目の特性は、CRCレジスタの現在の値の1の補数を入力するというものです。1-Wire CRCアルゴリズムの場合、結果として得られるCRC値は常に35 (16進数)すなわち53 (10進数)です。この理由は、表2に示すとおり、1の補数データが入力されたときのCRCレジスタの動作に注目することによって説明することができます。

例1. アセンブリ言語による手順

DO_CRC:	PUSH ACC	;save accumulator
	PUSH B	;save the B register
	PUSH ACC	;save bits to be shifted
	MOV B,#8	;set shift = 8 bits ;

CRC_LOOP:	XRL A,CRC	;calculate CRC
	RRC A	;move it to the carry
	MOV A,CRC	;get the last CRC value
	JNC ZERO	;skip if data = 0
	XRL A,#18H	;update the CRC value
;
ZERO:	RRC A	;position the new CRC
	MOV CRC,A	;store the new CRC
	POP ACC	;get the remaining bits
	RR A	;position the next bit
	PUSH ACC	;save the remaining bits
	DJNZ B,CRC_LOOP	;repeat for eight bits
	POP ACC	;clean up the stack
	POP B	;restore the B register
	POP ACC	;restore the accumulator
	RET

例2. 1-Wire CRCの計算例

CRC Value	Input Value
00000000	0
00000000	1
10001100	0 2
01000110	0
00100011	0
10011101	0
11000010	0 0
01100001	0
10111100	0
01011110	0
00101111	1 C
00010111	1
00001011	1
00000101	0
10001110	0 1
01000111	0
10101111	0
11011011	0
11100001	0 8
11111100	1
11110010	1
11110101	1
01111010	0 B
00111101	1
00011110	1
10000011	0
11001101	0 1
11101010	0
01110101	0
10110110	0
01011011	0 0
10100001	0
11011100	0
01101110	0
00110111	0 0
10010111	0
11000111	0
11101111	0
11111011	0 0
11110001	0
11110100	0
01111010	0
00111101	0 0
10010010	0
01001001	0
10101000	0
01010100	0 0
00101010	0
00010101	0
10000110	0
01000111	0 0
10101101	0
11011010	0
01101101	0
10111010	0 0
01011101	0
10100010 = A2 hex = CRC Value for [00000001B81C (Serial Number) + 02 (Family Code)]
10100010	0
01010001	1
00101000	0 2
00010100	0
00001010	0
00000101	1
00000010	0 A
00000001	1
00000000 = 00 hex = CRC Value for A2 [(CRC) + 00000001B81C (Serial Number) + 02 (Family Code)]

例3. 1-Wire CRCのルックアップ機能

Var
	CRC : Byte;
Procedure Do_CRC(X: Byte);
{
	This procedure calculates the cumulative Maxim 1-Wire CRC of all bytes passed to it.
The result accumulates in the global variable CRC.
}
Const
	Table : Array[0..255] of Byte = (

	0, 94, 188, 226, 97, 63, 221, 131, 194, 156, 126, 32, 163, 253, 31, 65,
	157, 195, 33, 127, 252, 162, 64, 30, 95, 1, 227, 189, 62, 96, 130, 220,
	35, 125, 159, 193, 66, 28, 254, 160, 225, 191, 93, 3, 128, 222, 60, 98,
	190, 224, 2, 92, 223, 129, 99, 61, 124, 34, 192, 158, 29, 67, 161, 255,
	70, 24, 250, 164, 39, 121, 155, 197, 132, 218, 56, 102, 229, 187, 89, 7,
	219, 133, 103, 57, 186, 228, 6, 88, 25, 71, 165, 251, 120, 38, 196, 154,
	101, 59, 217, 135, 4, 90, 184, 230, 167, 249, 27, 69, 198, 152, 122, 36,
	248, 166, 68, 26, 153, 199, 37, 123, 58, 100, 134, 216, 91, 5, 231, 185,
	140, 210, 48, 110, 237, 179, 81, 15, 78, 16, 242, 172, 47, 113, 147, 205,
	17, 79, 173, 243, 112, 46, 204, 146, 211, 141, 111, 49, 178, 236, 14, 80,
	175, 241, 19, 77, 206, 144, 114, 44, 109, 51, 209, 143, 12, 82, 176, 238,
	50, 108, 142, 208, 83, 13, 239, 177, 240, 174, 76, 18, 145, 207, 45, 115,
	202, 148, 118, 40, 171, 245, 23, 73, 8, 86, 180, 234, 105, 55, 213, 139,
	87, 9, 235, 181, 54, 104, 138, 212, 149, 203, 41, 119, 244, 170, 72, 22,
	233, 183, 85, 11, 136, 214, 52, 106, 43, 117, 151, 201, 74, 20, 246, 168,
	116, 42, 200, 150, 21, 75, 169, 247, 182, 232, 10, 84, 215, 137, 107, 53);

Begin
	CRC := Table[CRC xor X];
End;

表1. 1-Wire CRCを計算するためのテーブルルックアップの方法
Current CRC Value (= Current Table Index)	Input Data	New Index (= Current CRC xor Input Data)	Table (New Index) (= New CRC Value)
0000 0000 = 00 hex	0000 0010 = 02 hex	(00 H xor 02 H) = 02 hex = 2 dec	Table[2]= 1011 1100 = BC hex = 188 dec
1011 1100 = BC hex	0001 1100 = 1C hex	(BC H xor 1C H) = A0 hex = 160 dec	Table[160]= 1010 1111 = AF hex = 175 dec
1010 1111 = AF hex	1011 1000 = B8 hex	(AF H xor B8 H) = 17 hex = 23 dec	Table[23]= 0001 1110 = 1E hex = 30 dec
0001 1110 = 1E hex	0000 0001 = 01 hex	(1E H xor 01 H) = 1 F hex = 31 dec	Table[31]= 1101 110 = DC hex = 220 dec
1101 1100 = DC hex	0000 0000 = 00 hex	(DC H xor 00 H) = DC hex = 220 dec	Table[220]= 1111 0100 = F4 hex = 244 dec
11110100 = F4 hex	0000 0000 = 00 hex	(F4 H xor 00 H) = F4 hex = 244 dec	Table [244]= 0001 0101 = 15 hex = 21 dec
0001 0101 = 15 hex	0000 0000 = 00 hex	(15 H xor 00 H) = 15 hex = 21 dec	Table[21]= 1010 0010 = A2 hex = 162 dec
1010 0010 = A2 hex	10100010 = A2 hex	(A2 H xor A2 H) = hex = 0 dec	Table[0]=0000 0000 = 00 hex = 0 dec

CRCレジスタとその1の補数の組み合わせ

表2. CRCレジスタ値の入力
X₀	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₇*
1	X₀	X₁	X₂	X₃*	X₄*	X₅	X₆	X₆*
1	1	X₀	X₁	X₂*	X₃	X₄*	X₅	X₅*
1	1	1	X₀	X₁*	X₂*	X₃	X₄*	X₄*
0	1	1	1	X₀	X₁*	X₂	X₃	X₃*
1	0	1	1	0	X₀*	X₁*	X₂	X₂*
1	1	0	1	0	1	X₀*	X₁*	X₁*
0	1	1	0	1	0	1	X₀*	X₀*
0	0	1	1	0	1	0	1	Final CRC Value = 35 hex, 53 decimal
注：X_i* = X_iの補数

iButtonデバイス内でのRAMレコード用のCRC-16の計算

｢はじめに｣で説明したように、iButtonデバイスの中には、すべてのiButtonデバイスに存在する8バイトの一意のROMコードに加えて、RAMを持つものもあります。RAMには8バイトのROMコードに比べてより大きなデータ量が保存可能であるため、マキシムは、ROMの場合に使用する8ビットの1-Wire CRCの代わりに、16ビットのCRC値を使用してデータの完全性を保証することを推奨します。ここで推奨する特定のCRCは、一般的に、CRC-16と呼ばれています。シフトレジスタおよび多項式表現を図3に示します。図3から分かることは、16ビットCRCでは、16段がシフトレジスタに備わり、また多項式は16次の項を持つということです。先に述べたように、iButtonデバイスはCRC値を計算しません。ホストが値を生成し、実際のデータの末尾に16ビットCRC値を付加する必要があります。iButtonデバイスの｢通信チャネル｣、つまり金属接点の2つの表面の不確実性のため、データ転送には、一般的に3つのカテゴリに分類されるエラーが生じる可能性があります。1つ目は、短時間の断続的な接続が、データ内に少数のビットエラーを起こす場合で、通常のCRC-16機能はこのエラーを検出するように設計されています。2つ目のエラーは、接触が完全に失われたとき、たとえば、iButtonデバイスの読取り装置からの取外しが早すぎるときに発生するものです。

この場合は、iButtonデバイスの無接続がホストによって｢すべて1｣と解釈されるため、データの最後の部分がロジック1として読まれることになります。通常のCRC-16機能は、ほとんどの条件においてこの状況も検知可能です。3つ目のエラーは、読取り装置内での短絡によって発生するもので、このエラーは、iButtonデバイスが正しく挿入されていなかった場合、あるいは読取り装置内で大幅に傾いたことがある場合に起こる可能性があります。読取り装置の短絡の場合、ホストはデータをすべて0として読み取ります。これは、CRCを使用する際に問題を起こす原因となります。なぜなら、データの正しさを決定する方法は、データおよび保存されたCRC値を読み取り、ホストで計算して得られたCRCが0000 (16進数) (16ビットCRCの場合)であるかどうかを確認することであるからです。読取り装置が短絡されると、データおよびデータとともに保存されたCRC値はすべて0として読み取られ、誤った読取りが発生することになりますが、ホストが計算したCRCは、有効な読取りであると誤って示されます。この状況を回避するため、マキシムは、RAMに書き込まれたデータとともに、計算したCRC-16の値(CRC-16*)の補数を保存することを推奨しています。補数をとらないCRC-16の値を使用すると、iButtonデバイスからのデータの取出しは、1-Wire CRCのケースに類似したものになります。つまり、ホスト内のCRCレジスタが0000 (16進数)に初期化され、データおよびデータとともに保存されたCRC-16の値のすべてがiButtonデバイスから読み取られた場合、ホストが行う計算結果は、最終結果として、0000 (16進数)となるはずです。そうではなく、CRC-16の値の補数がiButtonデバイス内にデータとともに保存された場合、ホストでのCRCレジスタは0000 (16進数)に初期化され、実際のデータおよび保存されたCRC-16*の値が読み取られます。結果として得られたCRCの値は、有効な読取りに対してB001 (16進数)となるはずです。これによって、読取り装置の短絡によってだまされる可能性がなくなるため、システムの動作は大幅に改善されます。CRC-16機能がこれらの特性を持つ理由は、1-Wire CRCケースと類似した方法で示すことができます(図3と図5を参照)。16ビットのCRCの動作は、理論的には先に述べた8ビットの場合と同じですが、16ビット値がエラー検出に利用できるようになるため、CRCの特性は変更されています。CRC-16機能において検出可能なエラーのタイプは以下のとおりです。

データレコード内の任意の場所にある奇数個のエラーのすべて
データレコード内の任意の場所にあるダブルビットエラーのすべて
16ビットの｢ウィンドウ｣内に含まれる任意のエラー群(1～16ビットの誤り)
これより大きなエラー群のほとんど

図3. CRC-16のハードウェア図と多項式

CRC-16機能のハードウェア実装は、図3に示した機能図によって簡単にわかります。例4は、シングルビット演算を用いてCRC-16の値を計算する、ハードウェア動作に類似したソフトウェアソリューションを示しています。すでに述べたように、ルックアップテーブルを使用することにより、計算負荷を軽減するソフトウェアソリューションを実現することができます。8ビットの1-Wire CRCルックアップテーブル用に示した基本的な概念がCRC-16のケースにも有効です。ただし、8ビットのケースの方法に若干の変更を加える必要があります。なぜなら、CRC-16機能で得られる16ビット全体を前述のとおり1つのテーブルにマッピングした場合、このテーブルは2¹⁶または65,536エントリを持つことになります。また別の手法を例5に示します。ここでは、16ビットのCRC値を計算し、2つの256エントリテーブルに保存されています(一方は得られたCRCの高次バイトを、他方は低次バイトを格納)。現在の任意の16ビットCRC値(現在の高次バイトはCurrent_CRC16_Hiと表され、現在の低次バイトはCurrent_CRC16_Loと表される)、および新しい任意の入力バイトに対して、新しい高次バイトのCRC値(New_CRC16_Hi)を見つけるための、高次バイトテーブルへのインデックスを求める式を下に示します。

New_CRC16_Hi = CRC16_Tabhi[I] (I = 0～255)
ここで、I = (Current_CRC16_Lo) EXOR (入力バイト)

新しい低次バイトのCRC値(New_CRC16_Lo)を見つけるための、低次バイトテーブルへのインデックスを求める式を下に示します。

New_CRC16_Lo = (CRC16_Tablo[I]) EXOR (Current_CRC16_Hi) (I = 0～255)
ここで、I = (Current_CRC16_Lo) EXOR (入力バイト)

この方法の動作の仕組みについての例を図4に示します。

例4. CRC-16を計算するためのアセンブリ言語

crc_lo data 20h ; lo byte of crc calculation (bit addressable)
crc_hi data 21h ; hi part of crc calculation



;---------------------------------------------------------------------------
;	CRC16 subroutine.
;	- accumulator is assumed to have byte to be crc'ed
;	- two direct variables are used crc_hi and crc_lo
;	- crc_hi and crc_lo contain the CRC16 result
;---------------------------------------------------------------------------
crc16:			; calculate crc with accumulator
	push b	; save value of b
	mov b, #08h	; number of bits to crc.
crc_get_bit:
	rrc a	; get low order bit into carry
	push acc	; save a for later use
	jc crc_in_1	;got a 1 input to crc
	mov c, crc_lo.0	;xor with a 0 input bit is bit
	sjmp crc_cont	;continue
crc_in_1:
	mov c, crc_lo.0	;xor with a 1 input bit
	cpl c	;is not bit.
crc_cont:
	jnc crc_shift	; if carry set, just shift
	cpl crc_hi.6	;complement bit 15 of crc
	cpl crc_lo.1	;complement bit 2 of crc
crc_shift
	mov a, crc_hi	; carry is in appropriate setting
	rrc a ; rotate	it
	mov crc_hi, a	; and save it
	mov a, crc_lo	; again, carry is okay
	rrc a ; rotate	it
	mov crc_lo, a	; and save it
	pop acc	; get acc back
	djnz b, crc_get_bit	; go get the next bit
	pop b	; restore b
	ret
	end

例5. 参照テーブルを用いたCRC-16用のアセンブリ言語

crc_lo data 40h	; any direct address is okay
crc_hi data 41h
tmp data 42h



;---------------------------------------------------------------------------
;	CRC16 subroutine.
;	- accumulator is assumed to have byte to be crc'ed
;	- three direct variables are used, tmp, crc_hi and crc_lo
;	- crc_hi and crc_lo contain the CRC16 result
;	- this CRC16 algorithm uses a table lookup
;---------------------------------------------------------------------------
crc16:
	xrl a, crc_lo	; create index into tables
	mov tmp, a	; save index
	push dph	; save dptr
	push dpl	;
	mov dptr, #crc16_tablo	; low part of table address
	movc a, @a+dptr	; get low byte
	xrl a, crc_hi	;
	mov crc_lo, a	; save of low result
	mov dptr, #crc16_tabhi	; high part of table address
	mov a, tmp	; index
	movc a, @a+dptr	;
	mov crc_hi, a	; save high result
	pop dpl	; restore pointer
	pop dph	;
	ret	; all done with calculation
crc16_tablo:
	db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
	db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
	db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
	db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
	db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
	db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
	db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
	db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
	db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
	db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
	db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
	db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
	db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
	db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
	db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
	db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
	db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
	db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
	db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
	db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
	db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
	db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
	db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
	db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
	db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
	db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
	db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
	db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
	db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
	db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
	db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
	db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
crc16_tabhi:
	db 000h, 0c0h, 0c1h, 001h, 0c3h, 003h, 002h, 0c2h
	db 0c6h, 006h, 007h, 0c7h, 005h, 0c5h, 0c4h, 004h
	db 0cch, 00ch, 00dh, 0cdh, 00fh, 0cfh, 0ceh, 00eh
	db 00ah, 0cah, 0cbh, 00bh, 0c9h, 009h, 008h, 0c8h
	db 0d8h, 018h, 019h, 0d9h, 01bh, 0dbh, 0dah, 01ah
	db 01eh, 0deh, 0dfh, 01fh, 0ddh, 01dh, 01ch, 0dch
	db 014h, 0d4h, 0d5h, 015h, 0d7h, 017h, 016h, 0d6h
	db 0d2h, 012h, 013h, 0d3h, 011h, 0d1h, 0d0h, 010h
	db 0f0h, 030h, 031h, 0f1h, 033h, 0f3h, 0f2h, 032h
	db 036h, 0f6h, 0f7h, 037h, 0f5h, 035h, 034h, 0f4h
	db 03ch, 0fch, 0fdh, 03dh, 0ffh, 03fh, 03eh, 0feh
	db 0fah, 03ah, 03bh, 0fbh, 039h, 0f9h, 0f8h, 038h
	db 028h, 0e8h, 0e9h, 029h, 0ebh, 02bh, 02ah, 0eah
	db 0eeh, 02eh, 02fh, 0efh, 02dh, 0edh, 0ech, 02ch
	db 0e4h, 024h, 025h, 0e5h, 027h, 0e7h, 0e6h, 026h
	db 022h, 0e2h, 0e3h, 023h, 0e1h, 021h, 020h, 0e0h
	db 0a0h, 060h, 061h, 0a1h, 063h, 0a3h, 0a2h, 062h
	db 066h, 0a6h, 0a7h, 067h, 0a5h, 065h, 064h, 0a4h
	db 06ch, 0ach, 0adh, 06dh, 0afh, 06fh, 06eh, 0aeh
	db 0aah, 06ah, 06bh, 0abh, 069h, 0a9h, 0a8h, 068h
	db 078h, 0b8h, 0b9h, 079h, 0bbh, 07bh, 07ah, 0bah
	db 0beh, 07eh, 07fh, 0bfh, 07dh, 0bdh, 0bch, 07ch
	db 0b4h, 074h, 075h, 0b5h, 077h, 0b7h, 0b6h, 076h
	db 072h, 0b2h, 0b3h, 073h, 0b1h, 071h, 070h, 0b0h
	db 050h, 090h, 091h, 051h, 093h, 053h, 052h, 092h
	db 096h, 056h, 057h, 097h, 055h, 095h, 094h, 054h
	db 09ch, 05ch, 05dh, 09dh, 05fh, 09fh, 09eh, 05eh
	db 05ah, 09ah, 09bh, 05bh, 099h, 059h, 058h, 098h
	db 088h, 048h, 049h, 089h, 04bh, 08bh, 08ah, 04ah
	db 04eh, 08eh, 08fh, 04fh, 08dh, 04dh, 04ch, 08ch
	db 044h, 084h, 085h, 045h, 087h, 047h, 046h, 086h
	db 082h, 042h, 043h, 083h, 041h, 081h, 080h, 040h

図4. 計算の比較、およびCRC-16用のテーブル参照方法

興味深い中間的な方法を例6に示します。このコードは、図5に示す式を使用して現在のCRC値と入ってくるバイトの全体を処理することによって、CRC-16に入力される各バイトごとにCRC-16の値を生成しています。式の展開も示されており、現在の16ビットのCRCの値をアルファベット文字で示し、入力されるバイトのビットを数字で示しています。8シフト後の結果が、式として示されています。次にこれらの式を使用して、新しいCRC値の大部分をあらかじめ計算することができます。たとえば、数量ABCDEFGH01234567 (これらの全ビットのEXORとして定義)は、入ってくるデータバイトと現在のCRCの低次バイトのパリティです。この方法は、先に述べたビット単位やルックアップテーブルの方法に比べて、計算時間とメモリスペースが節約されます。最後に、テストケースとして使用可能なCRC-16機能の2つの特性について述べます。これは、前の方法のいずれについてもコードをデバッグするのに役立つものです。1つ目の特性は、1-Wire CRCのケースと同じです。CRCレジスタの現在の16ビットの内容を次の16ビットの入力としても使用した場合、結果として得られるCRCの値は、常に0000 (16進数)となります。CRC-16機能の2つ目の特性も、1-Wire CRCのケースと類似しています。CRCレジスタの現在の16ビットの内容の｢1｣の補数が次の16ビットの入力としても使用される場合、結果として得られるCRC値は、常にB0 01 (16進数)となります。これら2つのCRC-16の特性は、1-Wire CRCケースと同様の方法で証明されます。

例6. CRC-16の高速計算用のアセンブリ言語の手順

lo equ 40h ; low byte of CRC
hi equ 41h ; high byte of CRC



crc16:
	push acc	; save the accumulator.
	xrl a, lo
	mov lo, hi	; move the high byte of the CRC.
	mov hi, a	; save data xor low(crc) for later
	mov c, p
	jnc crc0
	xrl lo, #01h	; add the parity to CRC bit 0
crc0:
	rrc a	; get the low bit in c
	jnc crc1
	xrl lo, #40h	; need to fix bit 6 of the result
crc1:
	mov c, acc.7
	xrl a, hi	; compute the results for other bits.
	rrc a	; shift them into place
	mov hi, a	; and save them
	jnc crc2
	xrl lo, #80h	; now clean up bit 7
crc2:
	pop acc	; restore everything and return
	ret

図5. CRC-16の高速計算方法