PSoC 4200 Prototyping Kit (4)
PSoC4 の TCPWM コンポーネントの仕様を見ていて、「中国剰余定理」を使って 16 ビット・タイマ・カウンタを 32 ビット化し、キャプチャ機能により入力信号の周期を求めるレシプロカル周波数カウンタを作ろうと思い立ちました。
中国剰余定理の説明は次回以降に回しますが、簡単にいえば、値を知りたい「もとの数」は不明であるが、その数を複数の互いに素な法 (modulo) で割った余り (剰余: remainder) の組だけが得られる場合に、「計算で元の数が求められるよ」という話です。
48 MHz クロックでゲート・タイムを約 1 秒として測定するとカウンタに必要なビット幅は約 26 ビットとなり、TCPWM コンポーネントの 16 ビット・タイマ・カウンタ 1 個では足りなくなります。
TCPWM コンポーネントの構成では、2つのカウンタをカスケードにつなぐ、つまり、下位 16 ビット・カウンタのオーバーフローを上位の 16 ビット・カウンタでカウントする形式は実現しにくくなっています。
一方、同時にスタートさせるなどの並列動作は容易な構成です。
また、入力ピンには、いわゆる「ダブル FF」により「メタ・ステーブル状態」を回避する機能があり、2 つのカウンタのキャプチャが同じタイミングで行われることが保証されます。
16 ビット・カウンタを 2 個使用して 32 ビット・カウンタとして使うことは、ハードウェアとしては「普通」で損も得もないのですが、上位カウンタ部分をソフトウェアで実現すればハードとしては 16 ビット・カウンタ 1 個ですみます。
以前にも Arduino 用のレシプロカル周波数カウンタ用のスケッチでソフトによる 32 ビット化は経験ずみであり難しいわけでもなく、ハードで 32 ビット化することに実用的なメリットはないのですが、今回は中国剰余定理を使って実現してみたいという「興味本位」な理由で進めることにします。
中国剰余定理では一般的な場合を扱っていますが、「互いに素」な法の選び方によっては計算が非常に簡単になる場合があります。
n 進カウンタでクロックをカウントし続けた場合に、そのカウント値はリセット後からのクロック数を表す整数をカウンタの周期で割った余りと見なすことができます。
フリーランのバイナリ・カウンタでは周期は 2 のべき乗となります。
2 のべき乗は (それ以下の) 2 のべき乗でしか割り切ることはできませんから、もうひとつのカウンタを「奇数」に選べば 2 つのカウンタの周期は互いに素となります。
なぜなら、奇数は 2 では割り切れないので、当然 2 のべき乗でも割り切れません。
この「奇数」を 2 のべき乗マイナス 1 と選ぶと好都合です。
16 ビット・カウンタの場合、ひとつをフリーランの
m1 = 216 = 65536
と選び、もうひとつの周期をそれより 1 少ない
m2 = (m1 - 1 ) = (216 - 1) = 65535
と選びます。
「計算」で求められる数の範囲は 32 ビット・フルというわけではなく、
m1×m2 = m1×(m1-1) =(m1)2 - m1 = 232 - 216 = 4284801760
を法とする剰余になります。
つまり、32 ビットの「4 ギガ」個のうち最後の 64 Ki 個が「使えない」ことになります。
それでも 48 MHz クロックでカウントすると約 89 秒かかるので、カウンタがフリーランではまずいですが、周期測定のたびに両方のカウンタをリセットしてからカウントを開始すれば、ゲートタイムを 89 秒までは伸ばせることになります。
計算で求められるといっても、本当にそんなにうまく行くのかどうかを検証する C プログラムを下に示します。
#include <stdio.h> // modulo_1 = 2^16 = 65536 #define M1 (1UL << 16) // modulo_2 = (M1 - 1) = (2^16 - 1) = 65535 #define M2 (M1 - 1UL) #define M (M1 * M2) // Chinese Remainder Theorem calculation // for M1 = 2^16 = 65536 // M2 = (M1 - 1) = (2^16 - 1) = 65535 uint32_t crt_calc(uint16_t a1, uint16_t a2) { register uint32_t n; n = a2; n -= a1; n += (n >> 16); n = (n << 16) + a1; return(n); } // uint32_t crt_calc() int main( void ) { uint32_t n, k; uint16_t a1, a2; uint32_t match_cnt, err_cnt; match_cnt = 0; err_cnt = 0; fprintf(stdout, "Chinese Remainder Theorem test.\r\xa"); fprintf(stdout, "M1 = %u, M2 = (M1 - 1) = %u\r\xa", M1, M2); for (n = 0; n < M; n++) { // scan all number in modulo M a1 = (n % M1); // remainder 1 a2 = (n % M2); // remainder 2 // guess orignal number from two remainders k = crt_calc(a1, a2); if (k == n) { // matched match_cnt++; } else { // not matched err_cnt++; // error report fprintf(stdout, "n=0x%.8x, a1=0x%.4x, a2=0x%.4x, k=0x%.8x, (k-n)=%d\r\xa", n, a1, a2, k, k-n); } // if (k == n) { ... if (0 == (n % (M/32))) { // progress report fprintf(stdout, "match:%u = 0x%.8X, error:%u\r\xa", match_cnt, match_cnt, err_cnt); } // if (0 == ... } // for (n = 0; ... fprintf(stdout, "Total\r\xa"); fprintf(stdout, "match:%u = 0x%.8X, error:%u\r\xa", match_cnt, match_cnt, err_cnt); return(0); } // int main()
まず、もとの数を「n」として、for ループで 0 から 4284801759 までの有効な範囲のすべての数を発生させます。
次に m1 と m2 による剰余 a1, a2 を求め、中国剰余定理に基づく計算を行う crt_calc() 関数に渡してもとの値の推定値 k を求めます。
n と k が一致しなかった場合にはエラーの状況を出力します。
一致した場合にはカウンタ match_cnt をインクリメントだけして、特に出力は行いません。
最後に一致した回数と不一致の回数を出力します。
ただし、4 ギガ回の計算を行うのは時間がかかるので、エラーがない場合でも途中経過を出すようにしています。
出力結果 (の一部) を下に示します。
Chinese Remainder Theorem test. M1 = 65536, M2 = (M1 - 1) = 65535 match:1 = 0x00000001, error:0 match:134215681 = 0x07FFF801, error:0 match:268431361 = 0x0FFFF001, error:0 match:402647041 = 0x17FFE801, error:0 . . . . . <中略> . . . . . match:3892254721 = 0xE7FF1801, error:0 match:4026470401 = 0xEFFF1001, error:0 match:4160686081 = 0xF7FF0801, error:0 Total match:4294901760 = 0xFFFF0000, error:0
一致回数を見ると有効な範囲の数すべてが正しく求まっていることが分かります。
ちなみに、for 分の上限を M より大きな数にすると、正しく処理できる範囲を超えるので、増やした分だけエラーになります。
中国剰余定理に基づく計算をする関数は次のようになっています。
uint32_t crt_calc(uint16_t a1, uint16_t a2) { register uint32_t n; n = a2; n -= a1; n += (n >> 16); n = (n << 16) + a1; return(n); } // uint32_t crt_calc()
これを Keil/ARM の μVison v4.53 Lite で Cortex-M3/M4 (ARMv7-M アーキテクチャ) 向けにコンパイルした結果の逆アセンブラ・リストを下に示します。
0800111e <crt_calc>: 800111e: 1a09 subs r1, r1, r0 8001120: eb01 4111 add.w r1, r1, r1, lsr #16 8001124: eb00 4001 add.w r0, r0, r1, lsl #16 8001128: 4770 bx lr
計算部分は 16 ビット Thumb 命令 1 個と 32 ビット Thumb-2 命令 2 個の合計 3 命令にコンパイルされています。
点数を付けるなら 100 点です。 もっとも、良いコードが出るように C プログラムの書き方をいろいろ試した結果なので、当然といえば当然ですが。
PSoC Creator 3.0 SP2 に含まれる GCC V4.7.3 で Cortex-M0 (ARMv6-M アーキテクチャ) 向けにコンパイルした結果の逆アセンブラ・リストを下に示します。
00001468 <crt_calc>:
1468: 1a09 subs r1, r1, r0
146a: 0c0b lsrs r3, r1, #16
146c: 185a adds r2, r3, r1
146e: 0411 lsls r1, r2, #16
1470: 1808 adds r0, r1, r0
1472: 4770 bx lr計算部分は 16 ビット Thumb 命令 5 個にコンパイルされています。
Thumb 命令では ARM 命令や Thumb-2 命令とは違ってシフト・オペランドがないので、シフト部分は独立の命令で行っています。
点数を付けると 80 点ぐらいでしょうか。 r2、r3 を使っていますが、これはどちらか一方だけで済ませることができます。 ただし、r2、r3 は引数用途として破壊しても良いレジスタなので節約しても実用的な意味はありません。
