« 若いときに | Main | Rapid System Prototyping with FPGAs »

2007.12.05

好きなアルゴリズム

プアーなハードで作る貧乏くさいアルゴリズムが好き

RS-232C 調歩同期のパリティ
初期値の設定と1bitの保持xorで作れる超簡単回路。この回路で、7bitだろうが、8bitだろうが、20bitだろうがどの長さにも対応できるのが凄すぎる。

CRCチェック
これもFF並べて特定のbitのxorを取るだけ。エラー検出率と使用リソースのパフォーマンスが高すぎる。これもパケット長に依存しない。

線形補完のアルゴリズム
y = 3/5 x のような直線を書くとき、順に3を足していって5を超えたところでyを1増やすと良い感じで直線が書ける。
足すのに使う変数をアキュムレータのaとして、5を超えるとオーバーフローして、超えた分だけの値を保持する。

x y a
0 0 0 aに3を足す
1 0 3 次にaに3を足すと6になってオーバーフローするので、yを1増やし、aは6-5で1になる。
2 1 1 aに3を足す
3 1 4 次にaに3を足すと7になってオーバーフローするので、yを1増やし、aは7-5で2になる
4 2 2 次にaに3を足すと5になってオーバーフローするので、yを1増やし、aは5-5で0になる
5 3 0 以下繰り返し
6 3 3
7 4 1
割り算しなくても、加算器+レジスタで直線が引ける不思議。

TIFFフォーマット
FAXで使われるモノクロ、英文字を前提としたアルゴリズム。符号化/復号化にはラインメモリとラインプリンタだけでOK。一行前と同じラインなら数ビットで表現する優れもの。
エラーが発生しても改ページで立ち直れ!

イーサのCSMA/CD
とりあえず送信始めてみて駄目だったらお互いに適当に待ってもう一回送るだけ。この発想はなかなかできない。

ドルアーガのマップ生成
1バイトから、各フロアのマップ生成。1フロアが2画面なのはマッピー基板を使い回したから。

アルゴリズムじゃないけど、貧乏くさくて好きな物
ワイヤードORとか、モノクロのインペーダゲームにセロファンを張って色を付けるとか。

関係ないけど、調歩同期って死語じゃね?

|

« 若いときに | Main | Rapid System Prototyping with FPGAs »

Comments

Post a comment



(Not displayed with comment.)




TrackBack

TrackBack URL for this entry:
http://app.cocolog-nifty.com/t/trackback/18154/17281306

Listed below are links to weblogs that reference 好きなアルゴリズム:

« 若いときに | Main | Rapid System Prototyping with FPGAs »