barrel shifter

電子回路 日記

めも: anthy でんしかいろ→伝しかいろ

ふーん…
まあ K6 だったか PenPro だったかの最適化 manual に乗算が 2 cycle とか書いてあるから、shift 所要時間が shift 量非依存なのは当り前といえば当り前か。
とりあえず調べてみてこんなのが出てきた (紹介元) けど、のっけから私は基本的に

回　路　図　が　読　め　な　い

のでとりあえず wikipedia に逝って電子回路の context で muxer が何を指すか調べる。なるほろね。大体構造は想像がついたので自分で勝手に記号を決めながら適当に作図してみる。1 nibble in/out の 2 bit ctrl unsigned right shifter が手頃か。

入力を下 bit から 0, 1, 2, 3 と番号を振って、shift 量の上位 bit を a, 下位 bit を b とする。で、まず a を処理するために 0', 1', 2', 3' という内部的な一時出力を考えて

  • 0' := a ? 2 : 0
  • 1' := a ? 3 : 1
  • 2' := !a & 2
  • 3' := !a & 3

という風に muxer を 4 つ書く。間の配線はめんどいから省略。これらを同じノリで b にかけて

  • 0'' := b ? 1' : 0'
  • 1'' := b ? 2' : 1'
  • 2'' := b ? 3' : 2'
  • 3'' := !b & 3'

としてこれらを出力する。算術 shift にしたければ 2' := a ? 3 : 2, 3' = 3、などなど。

Naïve な実装そのものじゃねぇかコンチクショウ! 出力が安定するまでの時間が入力幅に対して線形に増えそげ。あほくさ。代数的に変換かけて減らせそうな気はするが。
そんなわけで考え直すが、いまいち効果的な方法を思いつかない。仕方ないので前出の PDF をちょっと読み進める。16-to-1 muxer とか書いてるんですが?

ところでここまで読みつづけてるアナタは奇特です。

よーく図を眺めてみるとこの 74x151 なる blackbox はどうやら 8 bit 入力の 3 bit 制御らしい。そんなん反則だ。二つ並べて NAND という構成から仕様を逆算することを試みる。制御の最上位 S3 とそれの反転が 74x151 に延びてる所からすると、多分出力の調整だろう。OUT 15 に繋がってる pair は、15:8 をもらうのがひとつと 7:0 をもらうのがひとつ。左 shift で bit は LSB から番号が振ってあると仮定すると、S3 が真なら出力は 7:0 のどれかに由来する (というか複製になる) はずなので、!S3 なら 15:8 の方の 74x151 の出力は入力に依存しないはず。

というわけで多分 74x151 は入力 8 bit の内 S[2:0] 番目の bit b を取り出して、S3 が真なら not b を出力、!S3 なら問答無用で 1 を出力、かな。実現方法は… b | S3 か。| が C の or に見えて仕方がない。
何だ殆ど何も習わなくても読めるじゃないか、回路図。

しかしこの NAND×2 の部分は、74x151 の出口を AND、二つの 74x151 の merge を OR、としても問題ないはず。微妙にわかりにくい NAND を使ってるのには何か理由があるのかな。電気的に得するとか。

まあそれ以前にここまでに晒した text だけで十分間違いだらけと予想されるのでもうやめよう。