適応フィルタを作ってみる
信号処理の分野では、適応フィルタが色々な目的で使用されています。ちょっとした理由で適応フィルタのプログラムを作ってみました。
- ADF【Adaptive Filter】
- 適応フィルタの構成
- 適応アルゴリズム
- サンプルコード：NLMSで作ってみる
- FIRフィルタ
- サンプルコード
- ADF
- サンプルコード
- FIRフィルタ
ADF【Adaptive Filter】
適応フィルタ【Adaptive Filter】とは、出力が目的とする信号に近づく（収束する）ように係数を自動で更新していく適応信号処理で、応用例として代表的なものはエコーキャンセラやノイズキャンセラだと思います。
適応フィルタの構成
適応フィルタの構成は、適応アルゴリズムとフィルタ部です。
フィルタ部でd(n)に似たy(n)を合成、
入力x(n)と誤差e(n)に基づいて、フィルタ係数h(n)を最適係数に近づけます。
誤差e(n)のパワーを最小にする。
続きを読む思考のサルベージ(その７)
各工程で心がけたい思想を掘り起こしてみる
システムテスト工程末期、客先リリース直前での不具合修正と性能変化ついて考えます。
ちょっとした判定ミス
SWの動作としてはよくあるやつで、メインループで、実行命令を受信し、命令内容に従いHWを設定して後は命令実行完了の応答送信までHW任せ、次の実行命令が来ていれば同じことを繰り返し、来ていなければいったんsleep状態に入ります。 今回は、「特別なケース」の考慮が漏れていて、不具合につながっていました。
影響範囲
客先リリース直前です、不具合が直ればそれで良いとはなりません。修正による影響範囲を明確にしなければなりません。処理性能の側面でも考慮が必要です。今回は、メインループの中に判定分を1つ追加し、「特別なケース」の場合に関数コールをするという数ステップの修正で、他の不具合を引き起こすような修正ではありません。また、「特別なケース」は性能測定対象外なので、追加した判定分1つのオーバーヘッドは乗りますが、大きな性能劣化には繋がらないと判断されました。
思わぬ結果
不具合は解消されましたが、処理速度としては不利となるオーバーヘッドが増える修正なのに、何故か処理性能が数パーセント向上してしまいました。修正の結果必要な処理がスキップされている可能性も考えられます。逆に性能が劣化していれば、よけな処理が活性化している場合もあります。 調べてみると、オーバーヘッドが効いて、ループ処理の中の実行命令の受信タイミングが変わり、毎周期行われるようになり、sleepに入ることがなくなっていました。結果的に全体としての処理性能が向上していたのです。
HW依存
HW依存が大きい処理系では、ちょっとしたタイミングのずれで、処理性能に影響が出てしまいます。テスト工程初期であれば、さほど問題視されませんが、客先リリース前ともなると、例え性能が向上したとしても、もちろん劣化したとしてもですが、原因の究明は必須です。大切なことは、事前にあらゆる可能性を考慮し、起こりうることを見極めることです。
何か掘り起こせた？
- HW依存の大きい処理系では処理タイミングを考慮することが重要。
- 性能の変化点では、要因の究明は必須。
必要な修正は実装しなければいけないのだから、性能目標さえクリアしていて、論理的な説明さえできればなんの問題もありません。
おしまい
誤ってループ処理千回余計にやってました、なんて言ったら大目玉ですけどね。
Cannot set LC_XXX to default locale: No such file or directory
はじめに
ことあるたびに目にする、
Cannot set LC_ALL to default locale: No such file or directory
のメッセージ。検索率の高いエラーメッセージなので、回避策？をここに記す。
続きを読むMIPSとMCPS(?)、100MIPSは100MHzで動くか？
信号処理とMISP（前編・後編）では、ソフトウェアのベンチマークとしてMIPS【Million Instructions Per Second 】が使われることについて書いてきました。
前編（信号処理とMIPS - Smile Engineering Blog）
後編（信号処理とMIPS・後編 - Smile Engineering Blog）
もう少し突っ込んだ話をしますと、実は開発の現場ではMIPSでちょっと困る話があります。
命令数を指標としても1命令にどれくらいの時間*1がかかるのかによって実際の処理量（演算量）が変わるからです。そこで、あまり馴染みのない言葉かも知れませんが、MCPS【Million Cycles Per Second 】という表現をご存知でしょうか・・・
ここで「MCPS」という略語がスタンダードなものとして定着しているか？には賛否あると思いますが、本記事に関しては【Million Cycles Per Second 】の略として使用したいと思います。
MCPS【Million Cycles Per Second 】とは？
まずMIPSですが、
MIPS計算
そのソフトウェアが何命令か、Million Instructions Per Second なので1秒間に何百万命令か？ということですが、デジタル信号処理のソフトウェアを考えたとき、MIPS計算は次の式になります。この時のフレームサイズとはサンプル数です。
MIPS = 命令数 × サンプリング周波数 / フレームサイズ ×
MCPS計算
命令数をサイクル数に置き換えただけです。
MCPS = サイクル数 × サンプリング周波数 / フレームサイズ ×
ソフトウェアの演算量を表す時にMIPSという言葉を使う場合が多いですが、実際のところは命令数ではなくサイクル数による計測が多いです。命令数を測定した場合（または算出した場合）MIPSになりますが、実際のところは1命令に何サイクルかかるかによってMIPSの意味が変わります。
ソフトウェアに求められるMIPSとは、100MIPSは100MHzで動くか？
*1:サイクル数
The Continuing Story of Error Correction Code
はじめに
最近、思うところがありエラー検出・訂正を勉強しています。
ネットの情報や書籍を頼りにやっていますが本格的なところは、行列だ、ベクトルだ、線形代数だ、巡回符号がどうのこうので多項式がなんとかで、挙句の果てはガロアなんとかだ、ときて心が折れます。それぐらい知っていてあたいまえだよね、というスタンスです。Wikipediaを見てもそんな感じですよね。 意味不明な数学記号のあめあらしです。
一番嫌なのは「当然こうなる」、「明白である」、「証明はここではしない」のようなパターン。独学だと聞く相手もいないので、例え「こういうことかな」と思ってもそれが正しいのか、はたまた間違っているのかわからない。 ひたすら試行錯誤。
反対に、数式を使わずに説明する、みたいなのもありますが数式を使わないで説明できるのはせいぜいハミング符号ぐらいまでで、CRCやBCHぐらいになるともう数式使わないと、もう無理。理解には程遠いものになってしまいます。
じゃあ、どうすりゃいいんだよ、となりますね。という訳で本ブログでは
- ちょっとだけ本題を進める。
- それについてちょっとだけ数学的に考察してみる。
- 以下、繰り返し。
という方針で進めていこうかと思います。 数学知識が必要になったら説明し、証明が必要なら都度書いていく。他のサイト、書籍参照はしない。
こんな感じで自分が躓いたところ、悩んだところを思い出しながら、ひたすら書き綴っていきたいと思います。
今回は数学的要素一切なしエラー検出事始めです。
では、エラー検出・訂正の終わらない話、はじまりはじまり。
何もしないと何が起こるか
４ビットのコードを送ってみる
まずは４ビットのコードを相手に送ることを考えてみます。
４ビットのコードなので全部で１６種類あります。送信側から４ビットのコードを通信路に入力します。受信側は通信路から４ビットのコードを受け取ります。通信路と書きましたが、通信でなくても、例えばメモリに書いた、読んだでも良いし何かバイナリのデータを入れて、取り出すといったものを考えてください。
完璧な通信路で送ってみる
最初は通信路として絶対に間違うことのない完璧なものを使ってみます。
| 送信 | 受信 | 送信 | 受信 | |
|---|---|---|---|---|
| ００００ | ００００ | １０００ | １０００ | |
| ０００１ | ０００１ | １００１ | １００１ | |
| ００１０ | ００１０ | １０１０ | １０１０ | |
| ００１１ | ００１１ | １０１１ | １０１１ | |
| ０１００ | ０１００ | １１００ | １１００ | |
| ０１０１ | ０１０１ | １１０１ | １１０１ | |
| ０１１０ | ０１１０ | １１１０ | １１１０ | |
| ０１１１ | ０１１１ | １１１１ | １１１１ |
送信したコードと受信したコードは完全に一致しています。素晴らしい！！
あたりまえですね。通信路は入力したものを間違いなく出力してくれるのだから入力と出力は一致します。
怪しい通信路で送ってみる
次に怪しい通信路を通してコードを送信してみます。怪しい通信路なのでたまに１と０を取り違えることがあります。
- 入力：００００
- 出力：００１０
００００を入力したのに受け取ったのは００１０でした。別のコードになっていますね。今は入力が００００だったよ、と分かっているので「あぁ、間違ってるな」とわかりますが送信側が何を送ったか知らなければ間違っていることに気づかないわけです。
そもそも何がいけないのか？
ここでは１ビットだけデータが変化したのですがデータが１ビット変化した結果のコードも有効なコードなわけです。４ビットで表すことのできる１６通りのコードすべてが有効なコードなのですから１ビット誤っただけでも別のコードになってしまう訳ですね。
これでは絶対に誤りに気づくことはできません。
何か知らんが魔法をかけて送ってみる
上の例では４ビットのコードをそのまま送っていましたが今回は４ビットのコードに魔法をかけて送ってみます。魔法をかけるのが符号器、魔法を解くのが復号器とします。 魔法をかける復号器は入力されたデータを以下のような５ビットのデータに変えてしまいます。
| 入力データ | 魔法のかかったデータ |
|---|---|
| ００００ | ０００００ |
| ０００１ | ０００１１ |
| ００１０ | ００１０１ |
| ００１１ | ００１１０ |
| ０１００ | ０１００１ |
| ０１０１ | ０１０１０ |
| ０１１０ | ０１１００ |
| ０１１１ | ０１１１１ |
| １０００ | １０００１ |
| １００１ | １００１０ |
| １０１０ | １０１００ |
| １０１１ | １０１１１ |
| １１００ | １１０００ |
| １１０１ | １１０１１ |
| １１１０ | １１１０１ |
| １１１１ | １１１１０ |
魔法を解く復号器は受け取った５ビットのデータを以下のように変換します。
| 魔法のかかったデータ | 受信データ |
|---|---|
| ０００００ | ００００ |
| ００００１ | ？ |
| ０００１０ | ？ |
| ０００１１ | ０００１ |
| ００１００ | ？ |
| ００１０１ | ００１０ |
| ００１１０ | ００１１ |
| ００１１１ | ？ |
| ０１０００ | ？ |
| ０１００１ | ０１００ |
| ０１０１０ | ０１０１ |
| ０１０１１ | ？ |
| ０１１００ | ０１１０ |
| ０１１０１ | ？ |
| ０１０１０ | ？ |
| ０１１１１ | ０１１１ |
| １００００ | ？ |
| １０００１ | １０００ |
| １００１０ | １００１ |
| １００１１ | ？ |
| １０１００ | １０１０ |
| １０１０１ | ？ |
| １０１１０ | ？ |
| １０１１１ | １０１１ |
| １１０００ | １１００ |
| １１００１ | ？ |
| １１０１０ | ？ |
| １１０１１ | １１０１ |
| １１１００ | ？ |
| １１１０１ | １１１０ |
| １１１１０ | １１１１ |
| １１１１１ | ？ |
完璧な通信路で送ってみる
ではデータを送ってみましょう。 まずは完璧な通信路を通してみます。 入力するデータは００１０です。符号器に００１０を入れると魔法がかかって００１０１になります。 完璧な通信路なので通過した後も００１０１のままです。 では受け取ったデータ００１０１を復号器をつかって魔法を解きます。 表の００１０１を探すと００１０ですね。正しく受け取れました。
怪しい通信路で送ってみる
次は怪しい通信路を通してみます。 入力するデータは００１０です。符号器に００００を入れると魔法がかかって００１０１になります。 怪しい通信路を魔法のかかったデータが通過していきますが００１０１が１０１０１になったとします。 １ビット変化していますね。 では受け取ったデータ００１０１を復号器をつかって魔法を解きます。 表の１０１０１を探すと・・・、？になっています。間違いにきづいたようですね。
何故間違いに気づくようになったのか？
「おまえが言うところの魔法とやらをかけたからだろ、しかも魔法ったってただの偶数パリティじゃねーかよ！！」
はいそうです。
でも、ここに重要なポイントがあります。
魔法が何かはとりあえず脇に置いといて、符号器が何をしたかを見てみましょう。
入力コードは４ビットでしたが、符号器の出力は５ビットになっています。
４ビットのデータを５ビットにして送った 、ここが重要です。
上の例では魔法がかかったデータ００１０１が１０１０１になった、としましたが魔法がかかったデータは５ビットあるので通信路で誤るビットの位置も５通りあるはずです。
- ００１０１ → １０１０１
- ００１０１ → ０１１０１
- ００１０１ → ００００１
- ００１０１ → ００１１１
- ００１０１ → ００１００
この５通りのデータを復号器で魔法を解くとすべて？になります。表を確認してみてください。
この魔法はデータが正しければ正しいデータ、１ビット誤った場合はすべて？にマッピングしているのです。
通信路に送り出すデータを４ビットから５ビットに増やすことにより表現できるビットのパターンは２倍になります。
この２倍に増えたビットパターンの空間で誤りのない正しいデータは正しいデータに、１ビット誤ったデータは？のデータに割り当てる、これにより１ビット誤ったよ、ということが認識できるようになるのです。
ビット数を増やして正しいデータの割り当てられる領域以外の領域を増やす、そしてその正しいデータが割り当てられたパターン以外の場所に誤ったパターンを割り当てる。この割り当て方で色々なエラー検出が生み出されるのではないでしょうか。
自分が思っていたイメージとは違った・・・
エラー検出・訂正というのは正しいデータ列の後ろに何か数学の魔法で計算した謎のビットを付ける、この謎のビットからエラーが検出・訂正できるんだ、って思っていたんですよ。今回の例で言えば
Dは入力データでPが謎のビット。
この謎のビット がすべてを解決してくれる、と。
でも、今回の話からすると符号器は入力データが占める領域よりも広い領域に正しいデータをマッピングして復号器がそれを元に戻す。元に戻す際に正しいデータではない値に復号されたら、それは通信路で何か間違えている、と判断する。
とすれば元のデータをどのようにマッピングするか、という問題なので符号器の出力（通信路を通るデータ）が入力データの後ろに謎のビットが付く、という形でなくても良い、ということなのでは。
思考のサルベージ(その６)
各工程で心がけたい思想を掘り起こしてみる
「単体テスト」について考えてみましょう。各工程のなかでは割と地味な作業ですが、この作業に割り当てられる時間は全体スケジュールに大きく響いてきます。
いつやるの？
V字モデルに従えば、
ですね。 ただ、私が経験した開発現場ではコーディング後にちゃんと単体テストの時間をとるところは少ないですね。実装がすんだらひとまず動かしそのまま結合テストへ、そしてBug対応が優先され、結局単体テストは後回しというケースが多いです。
何をどれだけやるの？
いろんな考え方があると思いますが、「単体テスト」を関数単位のホワイトボックステストと考えましょう。テスト項目は詳細設計書から作るということになります。ただそうなると、全ての関数に対して関数仕様書が必要です。詳細設計の期間にそれだけの事をする時間は正直ありません。結局時間の制約で、コードからテスト条件を起こして最低限カバレッジ100パーセントを目指すなんて本末転倒な作業になることが割と当たり前に起きますね。
ほんとの目的は？
当たり前のことですが前工程は後工程をスムーズに進めるためにあるということ。つまり、単体テストの目的は後工程の「結合テスト」に耐えうるように各関数、モジュールの品質を高めることにあります。
後付けの単体テストに意味はあるか？
本来の目的は果たせませんね。ただ、後工程に突入したとしても、関数、モジュール単位の「品質を高める」という作業は無駄ではありません。「ただの儀式」と考えて、やっつけ仕事にしないように心がけたいですね。
何か掘り起こせた？
- 本来の目的は「結合テスト」に耐えうるように各関数、モジュールの品質を高めること。
- 後付けになったとしても、各関数、モジュールの品質を高めるという目的は変わらない。
おしまい
V字モデルできちっとやれたら気持ちいいでしょうね。 いろいろなジレンマを抱えながら、多くの人がこれからも「単体テスト」に立ち向かっていくのでしょう。
