排他的論理和（exclusive OR） その２

排他的論理和の話をもう少し。
今回は主にアセンブラで使われる手法です。

A=Bの時、

A XOR B = 0

となりました。

つまり、

A XOR A = 0

です。

あるレジスタAXを０でクリアしたい場合、素直に記述すると

MOV AX, 0

となりますが、排他的論理和を使うと

XOR AX, AX

のように書くことができます。

何が嬉しいのかというと、まず"0"というリテラルを記憶しておく容量を節約できます。
あと、CPUによっては後者のほうが実行速度が速くなるかもしれません。
アセンブラの仕様にもよるので一概には言えないかもしれませんが、まあそんな感じです。

排他的論理和のもうひとつ重要な特徴が
同じ値で２回演算すると元の値に戻るということです。
つまり、

(A XOR B) XOR B = A

となります。

この特徴を利用すると、値の交換を行う際に一時的な値の退避場所が不要になります。

ある２つの値xとyを交換するとき、一般的な方法は次のようになります。

１．tempにyの値を代入

２．yにxの値を代入

３．xにtempの値を代入

この場合、xとy以外に一時的に値を退避しておくための記憶場所が必要になります。

しかし排他的論理和を使うと次の手順で値の交換をすることができます。

１．xにx XOR yの演算結果を代入

２．yにx XOR yの演算結果を代入

３．xにx XOR yの演算結果を代入

つまり、次のような記述で値の交換が可能です。

XOR AX, BX
XOR BX, AX
XOR AX, BX

はじめて見ると不思議かも知れませんが、
じっくりを追っかけていけば理解できると思います。

DoxygenがVHDLをサポート

Doxygen開始支援VHDL了

Gary的Digital Design日誌から。

中国語を読めるわけではありませんが見たままですね。

DoxygenでVHDLがサポートされるようになったとのこと。

なぜ、Verilog HDLよりも先に…

試していないのでどんな感じかはわかりません。
最近VHDLを使ってないので。

VHDL使いの方は一度試してみては？

排他的論理和（exclusive OR） その１

ある２つのデータAとBが一致すること
つまり、

A = B

を確認する回路をVerilog HDLで記述するにはどう書けばよいでしょうか？

assign equal = (A==B) ? 1'b1 : 1'b0;

こんな記述が一番妥当なところでしょうか。

ではもう少し具体的にどのような回路で構成されているか
わかるように記述するとどう書きますか？

A - B = 0

なので、次のように書けそうです。
（リダクション演算子については前回を参照）

assign equal = ~|(A - B);

しかし、データの比較のためにわざわざ減算器が登場するのも。。。

そこで、排他的論理和（exclusive OR）です。
ややこしい名前なので普通は"XOR"や"EOR"などと略します。

学生の頃、数学で習ったと思いますがXORの真理値表は次のとおりです。

真理値表

入力A	入力B	出力
0	0	0
0	1	1
1	0	1
1	1	0

0と0及び1と1の場合は0でそれ以外は1です。
つまり、２つが一致していれば0となり、異なれば1となります。

XORを使えば、

A XOR B = 0

となるので、次のような記述で２つのデータが一致しているかどうかを判断できます。

assign equal = ~|(A ^ B);

A ^ Bの演算結果は対応する各ビット毎のXORの結果となります。
つまり、C = A ^ Bとすると

C[0] = A[0] ^ B[0]
C[0] = A[1] ^ B[1]
…
C[i] = A[i] ^ B[i]

です。

ちなみに上記の３つの記述をXilinx ISEで論理合成にかけた結果、次のようになりました。
比較対照のA,Bはそれぞれ32bitとしています。
ターゲットデバイスは"xc3s1200e-4fg320"です。

【通常の比較】
Number of Slices: 8
Number of 4 input LUTs: 16

【減算による比較】
Number of Slices: 20
Number of 4 input LUTs: 40

【XORによる比較】
Number of Slices: 8
Number of 4 input LUTs: 16

普通に書くと、XORによる比較器が生成されるようですね。

高校生の頃だったと思いますが、数学の授業で初めて排他的論理和を習ったとき
名前もややこしいせいか、なんでわざわざこんな演算が必要なのだろうと感じましたが
この仕事をはじめてやっと、その意味がわかるようになりました。

別の仕事やってたらもう一生見なかったかもしれない。

リダクション演算子

Verilog HDLのリダクション演算子。

それほど頻繁に使うわけではないけれでも便利なもの。

たとえば次のように書くと（dataは複数ビットのバス）。

assign all_on = &data; // AND

assign bit_on = |data; // OR

assign parity = ^data; // XOR

all_onはdataの全てのビットが1の場合のみ1。

bit_onはdataのいずれかのビットが1でれば1。全てのビットが0の場合のみ0。

parityはdata中に奇数個の1がある場合は1。偶数個の1があある場合は0となる。

つまりそれぞれこんな感じ

all_on = data[0];
for (i=1; i < DATA_WIDTH; i=i+1) 
  all_on = all_on & data[i];  

bit_on = data[0]; 
for (i=1; i < DATA_WIDTH; i=i+1) 
  bit_on = bit_on | data[i];  

parity = data[0]; 
for (i=1; i < DATA_WIDTH; i=i+1) 
  parity = parity ^ data[i];

ビット幅を気にする必要がないので楽ですよね。