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

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

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

 

完成品・動作風景

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

動作風景

バブルソート回路できたーーー！！！ 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言語のプログラムを載せておきます。

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の 次の状態を論理関数で表現すると以下のようになります。

 

次に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表示部は回路図に載せていません。

 

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