2012年3月13日火曜日

AtmelAVRで8bitデータのパリティビット計算

WinAVRでプログラムを作成している場合、8bitのパリティビットの計算は <util/parity.h>  parity_even_bit(val) を使用すればすぐに実装で来てしまう。
しかしどうしても、1byteの塊になっているデータをどうやって要素ごとに排他的論理和をかけてパリティを計算してしているのか非常に興味が湧いたため考えてみた。



一般的にパリティビットの計算は、計算対象の書くビットを排他的論理和でつなげることで計算できる
n1 ~ n4 のデータがあるときは

parity bit = n1⊕n2⊕n3⊕n4

となる。

ここで問題になるのが、n1 ~ n3 というのは1バイトの塊の中の要素ということだ。
C言語で処理を記述している限り、これをスマートに実現する方法はパッと思い浮かばない。配列にしてしまえば楽勝だけれども、マイコンのプログラミングをしているのにそんな大味なことをする気にはならない。

そこでWINAVRのライブラリを覗いてみると、パリティビットの計算はインラインアセンブラで実現されていて、

(__extension__({                                        \
        unsigned char __t;                              \
        __asm__ (                                       \
                "mov __tmp_reg__,%0" "\n\t"             \
                "swap %0" "\n\t"                        \
                "eor %0,__tmp_reg__" "\n\t"             \
                "mov __tmp_reg__,%0" "\n\t"             \
                "lsr %0" "\n\t"                         \
                "lsr %0" "\n\t"                         \
                "eor %0,__tmp_reg__"                    \
                : "=r" (__t)                            \
                : "0" ((unsigned char)(val))            \
                : "r0"                                  \
        );                                              \
        (((__t + 1) >> 1) & 1);                         \
 }))
引用:http://www.nongnu.org/avr-libc/user-manual/group__util__parity.html#ga4180eaa9b8f27f8efc589f3a3ba1724c

のようになっている。パッと見意味がわからなかった。
そこでせこせこと面倒な計算をしてみたところ、解決した。

Scan3_

手書きで大変申し訳ない。
SwapとXOR命令処理の半分を行い、2回のシフトとXORで3/4の処理を行う。
そして加算とシフトと論理積で巧みに要素ごとのXOR相当の計算をしている。

情報工学をまじめに勉強したことはなかったので、こういう数学的に美しいものを見るとついワクワクしてしまう。そして記事にしてしまう。

気が向いたら推敲します。多分向かないけど・・・。

多分この記事は日本語として色々おかしいと思う。
日本語が不自由なのは勘弁していただきたいが、数学的・工学的間違いがあってどうにもと思ったらコメント等で指摘いただけるととてもありがたいです。

0 件のコメント:

コメントを投稿