バブルソートを行う電子回路を作ってみた

今回は CPU を用いずにハードウェアでバブルソートを行う回路を作ってみました。

ソート対象の変数はコンデンサに充電された電圧で、フリップフロップで状態管理、オペアンプで比較・代入を行います。

1 完成品・動作風景
2 全体の構成
3 コンデンサ及び制御部
4 状態計算部
5 状態遷移機械を電子回路で実現
6 クロック・リセット生成部
7 LED表示部
8 全体回路図

完成品・動作風景

どんなものを作ったのかイメージしやすいように、完成品を最初にお見せします。

動作風景

バブルソート回路できたーーー！！！ pic.twitter.com/0Eb0G1a4cG

— きっちー@3/4こっしぇる (@rikeden_net) December 28, 2022

ちなみに冒頭で CPU なしと書きましたが、各コンデンサの電圧を測定して LED を表示させる部分については PICマイコン及び LED制御IC を用いています。ごめんなさい。

全体の構成

このバブルソート回路はいくつかのブロックに分かれていて、図にするとこのような感じになります。

図中の矢印は信号の流れを表しています。

続いてそれぞれの部分について説明していきます。

コンデンサ及び制御部

まずは電子回路としてイメージしやすいコンデンサ等の部分から説明します。

コンデンサ及び制御部は下図のような構成になっています。左の n1, n2, S は外部からの入力で、右の rev は出力です。

図中の二重線は複数の線で繋がっていることを表しています。

コンデンサユニットは100uFのコンデンサと充放電用のタクトスイッチ2個で構成されます。ちなみに充電は 0.1mA の定電流ダイオードを通してゆっくり充電できるようにしてあります。

2個のアナログマルチプレクサにはそれぞれ状態制御部のカウンタからの選択信号 n1, n2 が入力されて、8個のコンデンサから 1個ずつ比較器と代入回路に接続します。

n1, n2 は 3bit の信号線で n1 = n2 + 1 の関係になっています。8個のコンデンサの電圧を V₀ ~ V₇ としたとき、V₀ < … < V₇ とするのが最終目標であり、比較器は V_n1 > V_n2 となっているときに交換が必要ということで rev = H を出力します。

代入回路は下図の構成になっています。

オペアンプとアナログスイッチのペアが 3つあり、外部からの制御信号 S1 ~ S3 (先の図における S)により一つずつ順番に動作するようにします。

このオペアンプはボルテージフォロワと呼ばれる回路で、非反転入力の電圧をそのまま出力します。これにより電圧のコピーが可能になります。

プログラムで 2つの変数 a, b を入れ替えるときは

① tmp = a;
② a = b;
③ b = tmp;

みたいなことをしますが、これと全く同じことを代入回路で行っていて、S1 ~ S3 が ① ~ ③ に対応しています。

状態計算部

次にこの回路の心臓部である状態計算部について説明します。

状態計算部はバブルソートのプログラムを状態遷移機械として考え、それをフリップフロップなどの記憶素子を用いて電子回路にしたものになります。

まずは電子回路は置いておきバブルソートの状態遷移機械を構成します。

参考までに C言語のプログラムを載せておきます。

while(1){
    int changed = 0;
    for (int i = 0; i < 7; i++){
        if (A[i] > A[i+1]){
            int tmp = A[i];
            A[i] = A[i+1];
            A[i+1] = tmp;

            changed = 1;
        }
    }
    if (changed == 0) break;
}

while(1){

int changed = 0;

for (int i = 0; i < 7; i++){

if (A[i] > A[i+1]){

int tmp = A[i];

A[i] = A[i+1];

A[i+1] = tmp;

changed = 1;

}

if (changed == 0) break;

}

2重ループの外側のループが一般的なバブルソートとは違うかもしれませんが、今回の回路の仕様に近付けているためです。

これを状態遷移機械で考えます。状態遷移機械とは現在の状態と外部入力から次の状態を計算する機械です。現在の状態と入力のすべての組み合わせに対して次の状態を定義することで状態遷移機械が定義できることになります。

ここでは状態として n1, n2, S, ch を持つものとします。n1, n2 は 4bit で 0 ~ 15 の値を取ります(実際に使うのは 0 ~ 8)。S は 4bit ですが、4bit のうち常にどれか 1つの bit が立っている(ワンホット)とし、S0, S1, S2, S3 の 4つの値を取ります。ch は 1bit で、L または H の値を取ります (changedの意)。

入力はリセット信号 R と、反転フラグ rev の 2つで、どちらも 1bit であり L または H の値を取ります。

ここで状態遷移機械は次の表で定義できます。ただし、X は任意の値を表し、現在の状態と次の状態の両方に X がある場合は値が変化しないとします。

この状態遷移機械の動作を順を追って確認してみましょう。

①リセット信号R = H のとき n1, n2, S, ch が初期化される。以後基本的に R = L であるとする。

② rev = L のとき (電圧の交換が不要なとき) n1, n2 の値をカウントアップする。

③ rev = H のとき電圧交換を行うために S を S1 ~ S3 に順に変化させる。(S1 ~ S3 は先の代入回路に繋がっている)

やることはこれだけですが、特に③で注意すべき点がいくつかあります。

まず電圧交換を行っている間は n1, n2 の値を変えないこと。また S3 から S0 に戻るときに ch を H にセットすること。

そして S = S0, rev = H の状態から電圧交換を行うと必然的に S = S1, S2, S3 を経由した後 S = S0, rev = L の状態になるということです。

これによりバブルソートの 2重ループの内側のループが表現されます。外側のループはリセット信号R によって表現することになります。(後述)

後で使う話ですが、内側のループの終了は n1 が 8 になったときで、これは n1 の bit3 (最上位ビット) が 1 になるということで判定できます。

状態遷移機械を電子回路で実現

一般的に状態遷移機械は組み合わせ回路とフリップフロップを用いることで実現することができます。

フリップフロップは 1bit の記憶素子で、クロックの立ち上がりの瞬間の入力を記憶して出力します。

組み合わせ回路とは内部に状態を持たず、入力だけで出力が決まる回路のことです。デジタル回路であれば論理ゲートを組み合わせたものになります。

状態遷移機械を実現するには状態や入力を全て bit単位で考え、図のような回路を作ります。フリップフロップの出力(現在の状態)と外部入力から組み合わせ回路でフリップフロップへの入力(次の状態)を計算し、クロックに合わせて状態を更新します。

あとやることは状態遷移図を論理関数で表現し、組み合わせ回路にすることです。

状態遷移図を再掲しておきます。

まずは S と ch について考えます。これらは n1, n2 には依りません。

S0 ~ S3, ch の次の状態を論理関数で表現すると以下のようになります。

S0′ = R + S0 R rev + S3 R = R + S0 rev + S3
S1′ = S0 R rev
S2′ = S1 R
S3′ = S2 R
ch’ = (ch + S3) R

次に n1, n2 ですが、こちらはフリップフロップではなくロード付き4ビットバイナリカウンタ (74HC163) を用いました。データシートより真理値表を抜粋します

このバイナリカウンタは同期ロード付きなので、R をカウンタの LD に繋げばリセット信号に合わせてカウンタの値を 0 や 1 にすることができます。

また、イネーブルピンもついているのでカウントの制御も可能です。ENP を H に固定しておくと、ENT = H のときのみカウントするようにできます。

先の遷移図より、ENTの論理関数は ENT = S0 R rev ですが、R = H のときはカウントよりもロードが優先されるので、 ENT = S0 rev で十分です。さらにこの式は S0′ の式の第2項と一致しているので流用することができます。

結果として状態制御部はフリップフロップとバイナリカウンタ、AND、OR、NOTゲートがあれば実現できることになります。

回路図は煩雑としているので、この記事の最後に回路全体のものを掲載します。

クロック・リセット生成部

クロックはNOTゲートによるリングオシレータとプッシュスイッチによる手動クロックの 2つを用意し、トグルスイッチによって切り替えられるようにします。

また、クロックにイネーブル信号による制御機能をつけ、ソートが完了したら自動的にクロックが停止するようにします。

ソートの完了は内側のループが終わったときに交換フラグの ch が L であることで判定することができます。よってクロック制御部は次のようになります。

なお、このフリップフロップの非同期セット、リセットピンにはプルアップ抵抗とタクトスイッチを付けておいて、手動でもクロック制御ができるようにします。

次にリセットですが、リセットは初めに手動で行う場合と内側のループ終了時にソートが完了していないときに自動で行う場合の 2つがあります。

これも非同期セット、リセット付きのフリップフロップで次のように作ることができます。

クロック制御の時と違うのは n1.bit3 がフリップフロップの入力ではなく出力側に繋がっているという点です。これはフリップフロップを挟んで信号が 1クロック分遅れるのを回避するためです。

リセット信号は非同期セットするか n1.bit3 から生成されるかのいずれかだけなのでフリップフロップの入力は L となっています。

リセット周りのタイミングチャートはこのような感じです。黄色い所でリセットがかかります。ch が H だった場合は CLKEN は H のままでもう一周処理が始まり、ch が L だった場合は CLKEN が L になり CLK は立ち上がってすぐに L になります。

1サイクル分だけ n1 が 8 となり、マルチプレクサは下位 3bit を見るので 0番目のコンデンサが選択されますが、次のサイクルではリセットがかかるのでコンデンサの値が変化することはありません。

LED表示部

コンデンサの電圧と内部状態を表示するために LED を付けて表示しています。クロックやフリップフロップの出力などにはそのまま抵抗と LED をぶら下げて可視化しています。

コンデンサの電圧については AD変換する必要があるので甘えてマイコンを使用しています。使用したのは PIC16F1579 で 9個のコンデンサの電圧を逐次測定して 0 ~ 10 の 11 段階に変換します。

この値を 10連バーLED で表示させるのですが、90個もの LED を制御するのはマイコンの残りのピンを使っても厳しいので、7セグLED制御ICの TM1637 を使用しました。

TM1637 は 6桁の 7セグLED を制御できるのですが、要するに 8 x 6 のマトリックスを制御できるということなので、90個の LED を 45個ずつマトリックス状に配線して 2個の TM1637 で制御させています。

PIC と TM1637 の間はクロック線(共通) 1本とデータ線それぞれ1本の計3本で接続できるので、PIC の残りのピンでも十分です。

全体回路図

最後に、バブルソート回路の回路図を掲載して締めたいと思います。

詳しく見たい方は画像をクリックしてください。別のタブで開くことができます。

なお LED表示部は回路図に載せていません。

最後までご覧いただきありがとうございました。