豊富な経験と実績を背景に、RFID製品やFPGA/LSI、通信システム等の開発・設計から試作・製品化までお客様の御要望にお応え致します。

前提

• ここでは当社で開発した技術資産を基にして書き下ろされた社員教育向けビタビ複号アルゴリズムついて解説します。このアルゴリズムは今では使われなくなったHD-DVDの複号用として使われていました。
  

1.基本構成

• ブランチメトリック算出は前の状態からそのときの状態までのブランチメトリックを算出するための機能ブロックです。
• ACS(Add-Compare-Select)は各状態での最尤パスを選択(Select)するための機能ブロックです。このブロックにはブランチメトリックの加算機能(Add)と最尤パスを選択するための比較機能(Compare)も含まれ、これらの工程を略してACSと呼びます。
• ACSメモリはACSブロックの結果をパスメトリックとして一時的にプールする領域です。
• パスメモリはACSで選択された最尤パスの履歴をプールする領域です。
• トレースバックはパスメモリにある最尤選択パスを逆順に辿って出力データバッファを用意する機能ブロックです。
• 
  　　　　　

2.ビタビ複号：演算ブロックの処理

2.1 入力データの取り扱い

• 入力データはデータサンプリング時刻と電圧レベルの２値のセットを１つのデータとして扱います。データサンプリング時刻、電圧レベルともに浮動小数点を仮定します。電圧レベルはビットデータをPR(1,2,2,2,1)による9レベル化に変換した値を表すものでなければなりません。9レベルの最大値、最小値は別途与えられるものとします。

2.2 ブランチメトリックの算出

• 入力データはデータサンプリング時刻と電圧レベルの２値のセットを１つのデータとして扱います。データサンプリング時刻、電圧レベルともに浮動小数点を仮定します。電圧レベルはビットデータをPR(1,2,2,2,1)による9レベル化に変換した値を表すものでなければなりません。9レベルの最大値、最小値は別途与えられるものとします。
• ブランチメトリックは対象とするブランチを通過すると考えたときの誤差量です。最小二乗法の考えを利用して、入力電圧レベルデータと0～8の信号レベルに対応した電圧レベルの差の2乗を採ります（他のパスと比較したときの相対的な値の大小が意味を持ち、計算量も抑えられる事からあえて平方根は求めません）。電圧レベルスライスは電圧レベル最大値、最小値が判明した時点で固定化します。求める式は BM(t, i) = ( y_t ? i )² です。
  ここで、tは時間、iは電圧出力レベル、y_t は 時間tでの入力電圧レベルです。
  

2.3 PR(1,2,2,2,1)に対応したビタビ復号の状態遷移表

• PR(1,2,2,2,1)に対応したビタビ復号の状態遷移図は以下のとおりです。 a/bは分子aは入力値、分母bは出力値です。S0xNは状態識別番号です。
• 
  
• これに相当するデータは実装アルゴリズム上では行列形式で以下のように保持する事が可能です。
• 
  

2.4 パスメトリックの算出(ACS)

• パスメトリックはその状態へ遷移する「累積ブランチメトリック最小値」です。状態遷移図からは、ある状態へ遷移するためにはどの状態から遷移するのかが判り、そのパスの最大数はPR(1,2,2,2,1)の場合、高々2パスです。ACSのAddは前状態でのパスメトリック(初期値0)とその状態へ遷移するためのブランチメトリックの和を採る事を意味します。Compare+Selectはある状態へ遷移するパスが複数あるとき、その中からブランチメトリックの最小値を選択する事を意味します。

2.5 トレースバックによる出力決定

• トレースバックのためにパスメモリを20個持ち、最終的に20個前の入力データに対して最尤電圧レベルの決定をします。トレースバックが長ければ最尤パスとそうでないパスとのパスメトリックの差が一層大きくなりますから、エラーに対する耐性も大きくなるのでトレースバック長は最尤データの信頼性を決定する重要な項目です。一般的に最適なトレースバック長は拘束長 の5倍(=25個)とする事が多い様ですが、ここでは20個とします。入力された最新のデータに対して最少のパスメトリック値からトレースバック開始状態がわかります。そして、その状態に遷移するためのパスはPR(1,2,2,2,1)の場合、高々2パスしかないことは既知なので、2つの最尤パス候補の内、より小さいメトリック値を持つ前状態から遷移したと考え、前状態を決定します。これを最古データまで行います。
• 新たな入力データがあったとき、最古データを1つ捨ててトレースバックします。パスメモリは入力データが無くなるまで20個のデータを保持します。入力データが20個未満の場合、満たされないデータ領域は無効とします。

2.6 出力データの取り扱い

• 出力データは内部状態0から始まり、ある状態においては次の状態に遷移する過程で出力レベルと入力データが状態遷移表から判定できます。これにより、出力データは入力データサンプリング時刻、最尤電圧レベルとします（他に最尤状態値、最尤入力レベルの出力が可能です）。

3. アルゴリズムの確認

• ここではサンプルデータCCFF0318を使って基本動作の机上確認をします。

3.1 PR(1,2,2,2,1)による符号化

• サンプルデータCCFF0318の入力は PR(1,2,2,2,1)によって1344444444578888753100134432344310に符号化されます。また、その状態遷移過程は136C936C937FFFFFEC8000136C8136C800となります。
• 
• このデータを-1.0から+1.0までの浮動小数点に割当て、レベルスライスを0.25とし、レベルと電圧の対応サンプルとして、ここでは以下のように定義します。

  レベル	0	1	2	3	4	5	6	7	8
  電圧	-1.00	-0.75	-0.50	-0.25	0.00	0.25	0.50	0.75	1.00

• ここで小さなノイズを付加した試験データを作成してみます。
• さらに意図的に３つのエラーを混入させてみます。

3.2 復号化

• 最初の20個のデータに対するブランチ・メトリックを計算してみましょう。なお、マークは最小値を表すものとします。 　　　　　
• 最初の20個のデータに対するパス・メトリックを計算してみましょう。 　

4 復号化のまとめ

• ○印はPR(1,2,2,2,1)符号化の状態遷移表からトレースバックの手法により決定された状態です。パスメトリック最小値の選択状態と状態トレースバックから得られる選択状態の結果は明らかに異なります。パスメトリックだけを頼りにするとエラーのある入力に対する状態判定は正しく出来ない事は上記の表から明らかです。PR(1,2,2,2,1)の状態遷移表からトレースバックの手法によって逆順に辿ることでパスメトリックだけでは判断できないエラーのある入力に対する状態も判定できる事が解りました。このことから、最尤入力データを得るには状態遷移入力値表を辿ればよく、最尤出力レベルを得るには状態遷移出力レベル表を辿ればよい事が解ります。

5 宣伝

• 当社では電子技術にまつわるお客さまの困り事に対応する受託開発も請け負っております。ご興味のある方は是非当社の担当窓口にご相談下さい。