論理回路２
井澤 裕司
前章では、 「modulo2」 の演算回路の構成法について学習しました。
本章では、この「modulo2」の演算の応用として、 「疑似ランダムパターン発生回路」 を紹介します。
「疑似ランダムパターン」（Pseudo Random Pattern） とは、 ０と１ で構成されるビット列であり、 携帯電話など通信路符号化の分野で広く用いられています。
０と１が一見ランダムに現れるように見えますが、 実際には一定の周期をもっています。
このような疑似ランダムパターンは、 modulo2 の除算による生成される 「循環小数」 と考えることができます。
一定の次数（本章で説明）の中で、 周期が最長となるものを 「M系列」 と呼んでいます。
この 「疑似ランダムパターン」 は、modulo2の除算回路、 すなわちシフトレジスタと排他的論理輪（EOR）で構成することができます。
一般に、この分野は 巡回符号 などの符号理論の中で解説されることが多いのですが、 本章ではModulo2の除算の応用という観点から説明します。
単なる理論として理解するのではなく、頭の中で具体的なイメージが沸くよう努力して下さい。
2.1 10進数の場合
10進数の除算では、割り切れる場合と、割り切れない場合があります。
例えば、6/5 = 1.2 の場合は少数を含めると割り切れます。
しかし、4/3 = 1.33333‥ の場合は 3が無限に続き、割り切れません。
割り切れない場合、その商は 循環小数 になります。
例えば、10/7 の場合は、以下のように 142857 という6個の数字のパターンが繰り返し現れます。
これは循環する形となるので、 シフトした 428571 や 285714 なども同じパターンに属します。
この例では、除算途中の余りが 0.000‥01 という値になる桁数で、その周期が決まります。
2.2 modulo2の場合
modulo2の除算でも、割り切れる場合と、割り切れない場合が存在します。
割り切れない場合は、循環小数の形になります。
modulo2の除算 [1000/1011] の例で確認してみましょう。
この場合、下の式で示すように、 7ビットの "0010111" というパターンが繰り返し現れます。
7桁ごとに除算途中の余りが、0.00‥01 という形になるため、周期は7になります。
なお、1周期の中で、 "0"が3回、"1"が4回現れます。
次に、別の除算の例を調べてみましょう。
[1000/1101] の除算では、次に示すように、 7ビットの "0011101" というパターンが繰り返します。
1周期の中で、"0"は3回、"1"は4回現れています。
実は、上で示した [1000/1011] のパターンの上位と下位を入れ替えたものとなっています。
今度は、周期が7以外になる例を示します。
同じ4ビットの除算、[1000/1001] では、以下のように商は循環小数の形になりますが、その周期は3です。
最後に、[1000/1100] の例を示します。
この商は、1が無限に続く形になります。
このように、modulo2の除算では、商が循環小数の形になることがありますが、 その周期は必ずしも一定ではなく、様々な値をとりえることがわかります
10進数の循環小数は、2進数に変換しても循環小数になります。
ところが、例えば10進数の 0.1 を 2進数に変換すると、 0.000110011‥ のように無限に続きます。
"1" と "0" の出現確率は10進数に依存し、必ずしも同じ値になるとは限りません。
いくつかの10進数小数を2進数に変換し、周期や"1" と "0" の出現確率がどのようになるか、調べてみましょう。（15桁までとします）
この作業は計算が進むにつれ必要な桁数が拡大してゆきます。
たとえ、コンピュータを用いたとしても、演算に必要なレジスタ長が増えてゆくため、 自ずと限界があることが納得できるでしょう。
しかし、modulo2の除算であれば、計算は比較的単純であり、 その回路構成も極めてシンプルになります。
前節では、modulo2の除算 (1000/1011) の商が、 1.01110010111‥ のような循環小数となり、
一定のパターン（1011100） を繰り返し出力することを示しました。
これを、7章で解説した除算回路を用いて実現することを考えます。
例えば （1000/1011） の除算を、 x3 / (x3+x+1) に置き換えて考えることができます。
下の式に示すように、 この商は 1+x-2+x-3+x-4+x-7+x-9+x-10+x-11+x-12+‥ のようになり、 （1011100） のパターンが繰り返します。
ここで、 1クロックの遅延を x-1 、a(x) = x3 とおくと、
上の除算が次のブロック図で実現できることがわかります。
以下、簡単に説明しましょう。
上の図から、次式が成立します。
これより、次式が得られます。
この除算回路の動作とタイムチャートを、以下の図に示します。
この図において、3個のD-FFの出力 （Q2、Q1、Q0） の値に注目して下さい。
入力 a(x) が "1" から "0" になるまでは、 （Q2、Q1、Q0） の値は （0、0、0） となっています。
すなわちリセット状態にあります。
しかし、 入力 a(x) が "1" から "0" に戻った後は、
（0、0、1）→（0、1、0）→（1、0、0）→（0、1、1）→（1、1、0）→（1、1、1）→（1、0、1）→ （ ‥ 以下繰り返し）
のようになっており、 （0、0、0） を除く7つのパターンが繰り返し現れています。
また、 （0、0、0） のパターンは2度と生じないことがわかります。
（Q2、Q1、Q0） の組み合せは、全部で 23 = 8 通り存在します。
これより、 （0、0、0） を除くすべてのパターンが1周期に1回、現れていることがわかります。
また、 出力 c(x) において、 "0" と "1" の発生する確率を求めると、 P["0"] = 3/7、P["1"] = 4/7 のようになります。
4.1 除算回路の入力部除去
modulo2の除算回路に一部変更を加えると、 「疑似ランダムパターン発生回路」 になります。
前節で示した除算回路をもう一度見て下さい。
入力 a(x) = x3 となっているので、 最初の1クロック（x3）だけ1であり、その後はすべて 0 です。
a(x) = x3 が 1から 0 になった後、D-FF出力 （Q2、Q1、Q0） には、 （0、0、0） を除くすべてのパターンが規則的に出現します。
この回路を除算としてではなく、 （1011100‥） のような一定のパターンを出力する回路として利用することを考えます。
3個のD-FFの出力 （Q2、Q1、Q0） が、（0、0、0） 以外の状態にあるとき、 入力 a(x) = 0 となっています。
すなわち、一旦この状態に入ってしまえば、実質的に入力 a(x) は不要であり、 クロックを与えるだけで、周期7のパターンを発生させることが可能です。
前節の回路から、入力と左の 排他的論理和（EOR） を除去すると、 「疑似ランダムパターン発生回路」 が得られます。
なお、3個のD-FFの出力が （0、0、0） となっている場合は、 常に出力 c(x) =0 となり、ランダムパターンは発生しません。
このため、初期設定や外部からのリセット信号により 、D-FFの出力がすべて "0" にならないような工夫が必要です。
教科書等に記載されている多くの回路図には、 このような初期設定が省略されていることが多いので、注意してください。
以下に、 x4/(x4+x+1) の割算回路を用いた 「疑似ランダムパターン発生回路」 を示します。
この回路では、周期15の 「疑似ランダムパターン」 が得られることがわかります。
3個のD-FFを用いた除算回路の場合、 ランダムパターンの周期は最大７となります。以下、その理由について説明します。
3個のD-FFの出力 （Q2、Q1、Q0） の組み合せは全体で 23 通り存在します。
したがって、 （0、0、0） を除くパターンは、 23-1 すなわち 7通りです。
例えば、 [1000/1011] の除算の場合 x3/(x3+x+1) となり、その出力は、
（0、0、1）→（0、1、0）→（1、0、0）→（0、1、1）→（1、1、0）→（1、1、1）→（1、0、1）
の7パターンになります。
出力のQ2は、
（0）→（0）→（1）→（0）→（1）→（1）→（1）
のように変化し、 その周期は7となります。
前節の例で示したように、 [1000/1101] の場合も周期は７ですが、分母の1、0の並びが逆になっています。
このとき、商の並びも逆になり "0011101" のようになります。
一方、 [1000/1001] や [1000/1100] の場合は、周期が 3 あるいは 1 になります。
一般に、除算の商の周期が最大値（ここでは７）になるとき、除算の分母の多項式を 「原始多項式」 と呼びます。
また、このような多項式により生成される 疑似ランダムパターン を 「M系列」 と言います。
例えば、次数が3のとき、
x3+x+1
x3+x2+1
が 原始多項式 になります。
以下、この2つの多項式の関係について整理してみましょう。
もう一度、 modulo2の除算 [1000/1011] に戻ります。
余りが、 0.00‥01 の形になる部分を抜き出して、 整数表示になるよう左へ4ビットシフトすると、次の式が得られます。
余り "1" を左へ7ビットシフトすると、 被除数 "10000000" になることに注意して下さい。
このとき、次の式が成立します。
右辺の +1 を移項すると、次のようになります。
これを 変数 x を用いて多項式表示すると、次のようになります。
ここで、 （x4+x2+x+1） は、 （x3+x2+1） （x+1） の形に因数分解できることを用いて変形しています。
なお、 （x3+x2+1） と （x3+x+1） は、これ以上因数分解することができないので、 既約多項式 と呼ばれます。
これより、 1/（x3+x2+1） と 1/（x3+x+1） はいずれも 周期 7 の循環小数 を生成することがわかります。
なお、 1/（x+1） の小数部はすべて 1 となり、周期は 1 です。
次数 n の原始多項式 の例を次の表に示します。
なお、3 以上の n について、 原始多項式 は複数存在するので注意して下さい。
表 原始多項式の例 （一部）
n 原始多項式 周期 1 x+1 1 2 x2+x+1 3 3 x3+x+1 7 4 x4+x+1 15 5 x5+x2+1 31 6 x6+x+1 63 7 x7+x3+1 127 8 x8+x4+x3+x2+1 255 9 x9+x4+1 511 10 x10+x3+1 1023 11 x11+x2+1 2047 12 x12+x6+x4+x+1 4095 13 x13+x4+x3+x+1 8191 14 x14+x10+x6+x+1 16383 15 x15+x+1 32767 16 x16+x12+x3+x+1 65535
例えば、 n=15 のとき、ランダムパターンの周期は 32767 となります。
これらは、15個のD-FFと 排他的論理和（EOR） 1個で構成することが可能です。
このように、次数を増やすことにより、実質的にランダムとみなせる "1" と "0" のパターンを比較的簡単に生成することが可能です。
５ まとめ
本章では、 疑似ランダムパターン発生回路の構成法 を中心に解説しました。
次章では、modulo2の除算のもう1つの応用として、 符号誤りを訂正する 「巡回符号の符号器、復号器」 の構成方法について紹介します。
論理回路2のトップページに戻る
