Smile Engineering Blog

ジェイエスピーからTipsや技術特集、プロジェクト物語を発信します

The Continuing Story of Error Correction Code

はじめに

最近、思うところがありエラー検出・訂正を勉強しています。

ネットの情報や書籍を頼りにやっていますが本格的なところは、行列だ、ベクトルだ、線形代数だ、巡回符号がどうのこうので多項式がなんとかで、挙句の果てはガロアなんとかだ、ときて心が折れます。それぐらい知っていてあたいまえだよね、というスタンスです。Wikipediaを見てもそんな感じですよね。 意味不明な数学記号のあめあらしです。

一番嫌なのは「当然こうなる」、「明白である」、「証明はここではしない」のようなパターン。独学だと聞く相手もいないので、例え「こういうことかな」と思ってもそれが正しいのか、はたまた間違っているのかわからない。 ひたすら試行錯誤。

反対に、数式を使わずに説明する、みたいなのもありますが数式を使わないで説明できるのはせいぜいハミング符号ぐらいまでで、CRCやBCHぐらいになるともう数式使わないと、もう無理。理解には程遠いものになってしまいます。

じゃあ、どうすりゃいいんだよ、となりますね。という訳で本ブログでは

  • ちょっとだけ本題を進める。
  • それについてちょっとだけ数学的に考察してみる。
  • 以下、繰り返し。

という方針で進めていこうかと思います。 数学知識が必要になったら説明し、証明が必要なら都度書いていく。他のサイト、書籍参照はしない。 こんな感じで自分が躓いたところ、悩んだところを思い出しながら、ひたすら書き綴っていきたいと思います。
今回は数学的要素一切なしエラー検出事始めです。

では、エラー検出・訂正の終わらない話、はじまりはじまり。

何もしないと何が起こるか

4ビットのコードを送ってみる

まずは4ビットのコードを相手に送ることを考えてみます。
4ビットのコードなので全部で16種類あります。送信側から4ビットのコードを通信路に入力します。受信側は通信路から4ビットのコードを受け取ります。通信路と書きましたが、通信でなくても、例えばメモリに書いた、読んだでも良いし何かバイナリのデータを入れて、取り出すといったものを考えてください。

完璧な通信路で送ってみる

最初は通信路として絶対に間違うことのない完璧なものを使ってみます。

送信 受信 送信 受信
0000 0000 1000 1000
0001 0001 1001 1001
0010 0010 1010 1010
0011 0011 1011 1011
0100 0100 1100 1100
0101 0101 1101 1101
0110 0110 1110 1110
0111 0111 1111 1111

送信したコードと受信したコードは完全に一致しています。素晴らしい!!
あたりまえですね。通信路は入力したものを間違いなく出力してくれるのだから入力と出力は一致します。

怪しい通信路で送ってみる

次に怪しい通信路を通してコードを送信してみます。怪しい通信路なのでたまに1と0を取り違えることがあります。

  • 入力:0000
  • 出力:0010

0000を入力したのに受け取ったのは0010でした。別のコードになっていますね。今は入力が0000だったよ、と分かっているので「あぁ、間違ってるな」とわかりますが送信側が何を送ったか知らなければ間違っていることに気づかないわけです。

そもそも何がいけないのか?

ここでは1ビットだけデータが変化したのですがデータが1ビット変化した結果のコードも有効なコードなわけです。4ビットで表すことのできる16通りのコードすべてが有効なコードなのですから1ビット誤っただけでも別のコードになってしまう訳ですね。
これでは絶対に誤りに気づくことはできません。

何か知らんが魔法をかけて送ってみる

上の例では4ビットのコードをそのまま送っていましたが今回は4ビットのコードに魔法をかけて送ってみます。魔法をかけるのが符号器、魔法を解くのが復号器とします。 魔法をかける復号器は入力されたデータを以下のような5ビットのデータに変えてしまいます。

入力データ 魔法のかかったデータ
0000 00000
0001 00011
0010 00101
0011 00110
0100 01001
0101 01010
0110 01100
0111 01111
1000 10001
1001 10010
1010 10100
1011 10111
1100 11000
1101 11011
1110 11101
1111 11110

魔法を解く復号器は受け取った5ビットのデータを以下のように変換します。

魔法のかかったデータ 受信データ
00000 0000
00001
00010
00011 0001
00100
00101 0010
00110 0011
00111
01000
01001 0100
01010 0101
01011
01100 0110
01101
01010
01111 0111
10000
10001 1000
10010 1001
10011
10100 1010
10101
10110
10111 1011
11000 1100
11001
11010
11011 1101
11100
11101 1110
11110 1111
11111

完璧な通信路で送ってみる

ではデータを送ってみましょう。 まずは完璧な通信路を通してみます。 入力するデータは0010です。符号器に0010を入れると魔法がかかって00101になります。 完璧な通信路なので通過した後も00101のままです。 では受け取ったデータ00101を復号器をつかって魔法を解きます。 表の00101を探すと0010ですね。正しく受け取れました。

怪しい通信路で送ってみる

次は怪しい通信路を通してみます。 入力するデータは0010です。符号器に0000を入れると魔法がかかって00101になります。 怪しい通信路を魔法のかかったデータが通過していきますが00101が10101になったとします。 1ビット変化していますね。 では受け取ったデータ00101を復号器をつかって魔法を解きます。 表の10101を探すと・・・、?になっています。間違いにきづいたようですね。

何故間違いに気づくようになったのか?

「おまえが言うところの魔法とやらをかけたからだろ、しかも魔法ったってただの偶数パリティじゃねーかよ!!」
はいそうです。
でも、ここに重要なポイントがあります。 魔法が何かはとりあえず脇に置いといて、符号器が何をしたかを見てみましょう。

入力コードは4ビットでしたが、符号器の出力は5ビットになっています。
4ビットのデータを5ビットにして送った 、ここが重要です。

上の例では魔法がかかったデータ00101が10101になった、としましたが魔法がかかったデータは5ビットあるので通信路で誤るビットの位置も5通りあるはずです。

  • 00101 → 0101
  • 00101 → 0101
  • 00101 → 0001
  • 00101 → 001
  • 00101 → 0010

この5通りのデータを復号器で魔法を解くとすべて?になります。表を確認してみてください。
この魔法はデータが正しければ正しいデータ、1ビット誤った場合はすべて?にマッピングしているのです。 通信路に送り出すデータを4ビットから5ビットに増やすことにより表現できるビットのパターンは2倍になります。 この2倍に増えたビットパターンの空間で誤りのない正しいデータは正しいデータに、1ビット誤ったデータは?のデータに割り当てる、これにより1ビット誤ったよ、ということが認識できるようになるのです。

ビット数を増やして正しいデータの割り当てられる領域以外の領域を増やす、そしてその正しいデータが割り当てられたパターン以外の場所に誤ったパターンを割り当てる。この割り当て方で色々なエラー検出が生み出されるのではないでしょうか。

自分が思っていたイメージとは違った・・・

エラー検出・訂正というのは正しいデータ列の後ろに何か数学の魔法で計算した謎のビットを付ける、この謎のビットからエラーが検出・訂正できるんだ、って思っていたんですよ。今回の例で言えば

 D_{4}  D_{3}  D_{2}  D_{1}  P_{1}

Dは入力データでPが謎のビット。 この謎のビット  P_{1} がすべてを解決してくれる、と。
でも、今回の話からすると符号器は入力データが占める領域よりも広い領域に正しいデータをマッピングして復号器がそれを元に戻す。元に戻す際に正しいデータではない値に復号されたら、それは通信路で何か間違えている、と判断する。
とすれば元のデータをどのようにマッピングするか、という問題なので符号器の出力(通信路を通るデータ)が入力データの後ろに謎のビットが付く、という形でなくても良い、ということなのでは。

という訳で、今回はここまで。
次回はここまでの話をちょっとだけ数学的要素を取り入れながら考えて、ハミング距離について考えてみます。

思考のサルベージ(その6)

各工程で心がけたい思想を掘り起こしてみる

単体テスト」について考えてみましょう。各工程のなかでは割と地味な作業ですが、この作業に割り当てられる時間は全体スケジュールに大きく響いてきます。

いつやるの?

V字モデルに従えば、

ですね。 ただ、私が経験した開発現場ではコーディング後にちゃんと単体テストの時間をとるところは少ないですね。実装がすんだらひとまず動かしそのまま結合テストへ、そしてBug対応が優先され、結局単体テストは後回しというケースが多いです。

何をどれだけやるの?

いろんな考え方があると思いますが、「単体テスト」を関数単位のホワイトボックステストと考えましょう。テスト項目は詳細設計書から作るということになります。ただそうなると、全ての関数に対して関数仕様書が必要です。詳細設計の期間にそれだけの事をする時間は正直ありません。結局時間の制約で、コードからテスト条件を起こして最低限カバレッジ100パーセントを目指すなんて本末転倒な作業になることが割と当たり前に起きますね。

ほんとの目的は?

当たり前のことですが前工程は後工程をスムーズに進めるためにあるということ。つまり、単体テストの目的は後工程の「結合テスト」に耐えうるように各関数、モジュールの品質を高めることにあります。

後付けの単体テストに意味はあるか?

本来の目的は果たせませんね。ただ、後工程に突入したとしても、関数、モジュール単位の「品質を高める」という作業は無駄ではありません。「ただの儀式」と考えて、やっつけ仕事にしないように心がけたいですね。

何か掘り起こせた?

  • 本来の目的は「結合テスト」に耐えうるように各関数、モジュールの品質を高めること。
  • 後付けになったとしても、各関数、モジュールの品質を高めるという目的は変わらない。

おしまい

V字モデルできちっとやれたら気持ちいいでしょうね。 いろいろなジレンマを抱えながら、多くの人がこれからも「単体テスト」に立ち向かっていくのでしょう。

Dask備忘録

はじめに

今回は、Daskを触ってみたので使い方を備忘録もかねてまとめてみます。

Daskとは

Pythonでデータ分析や機械学習をする際によく利用するライブラリがPandasですが、
Pandasで大容量データを処理すると、

  • データがメモリに収まらない
  • 基本的に単一スレッドで処理が行われるため処理速度が遅い

といった問題があります。
この問題を解決するのに並列・分散処理を行えるライブラリのDaskはよく利用されています。

Daskは主にNumPy、Pandas、PyToolzのAPIをもつデータ構造を提供しています。

API ベースパッケージ
Dask Array NumPy ndarray
Dask DataFrame pandas DataFrame
Dask Bag PyToolz
続きを読む

PyTorch超入門!

PyTorchを始めてみよう!

普段、TensorFlowで深層学習のソースを書いてた私……のはずなのですが、いろいろあってPyTorchを勉強する羽目(?)になってしまいました。が、

そもそもPyTorchなんてこれまでまったく触ったことないよ〜!!

これではあかん!!ということで、今回は勉強がてらPyTorchの超かんたんなプログラム(100ステップ未満!!)を書いてみることにしました。

そのお題とは、、PyTorchで論理演算!!!

f:id:jspnet:20191215214748p:plain

……って、なんてリソースの無駄使いなのでしょう(汗)

続きを読む

git worktree list を少しだけ使いやすく

はじめに

みんな大好き git-worktree。中でも list は使用頻度の高いコマンドですが、リスト後に cd することが多いのでこのような関数を利用しています。

続きを読む

初めての git-prompt

はじめに

git-worktree で複数のブランチを渡り歩いていると、今どこのブランチにいるのか?どんな状態なのか?がわからなくなることが多々あります。

プロンプトにブランチ名、状態を色で表現させる方法をご紹介します。git-prompt.sh のコメントの他、下記サイトを多分に参考にさせていただきました!

続きを読む

信号処理とMIPS・後編

ソフトウェアとMIPS

前編(信号処理とMIPS - Smile Engineering Blog)は、ハードウェアの性能を示すMIPS【Million Instructions Per Second 】について書きましたが、今回はソフトウェアのベンチマークとして書きたいと思います。

MIPS

コンピューターの処理能力を表す単位。コンピューターが1秒間に何百万回命令を実行できるかを示す。

前回も書きましたが、このような説明が多いです。

f:id:jspnet:20191015234008p:plain:left ソフトウェアの開発の要件として、信号処理では演算量(処理量)が必ず問われます。製品開発では、CPUをどれくらいのスペックにするかは言うまでもなく重要で、製品のコンセプトといっても過言でないでしょう。そのコンセプトを実現できるCPUを選定するのですが、売れる商品にするめにはコスト面も重要です。この辺の事情に非常に絡んでくるのがソフトウェアのリソースで、具体的には演算量とメモリサイズになります。

MIPS計算

そのソフトウェアが何命令か、Million Instructions Per Second なので1秒間に何百万命令か?ということですが、デジタル信号処理のソフトウェアを考えたとき、MIPS計算は次の式になります。

MIPS =命令数 × サンプリング周波数 / フレームサイズ × 10^-6

この時のフレームサイズとはサンプル数です。 FFT高速フーリエ変換)を例にすると、FFT長(点数)がフレームサイズです。大きければ演算量もメモリも大きくなります。

続きを読む