« ACE32のログ機能(画面入力編) | トップページ | ISDB-Tmm (携帯端末向けマルチメディア放送) »

2010年3月 9日 (火)

LDPC Staircase の勘どころメモ

LDPC(低密度パリティ検査符号)について書かれた RFC5170 についての勘どころを以下にメモとして残す。
なお、読者の理解度を上げることを目的としたため、トレードオフとして厳密度は下がることは了承願う(行列を参考資料のように0始まりにしているのではなく1行、1列始まりにしている等)。

----【2010年03月27日 追記】(ここから)----
 LDPC Staircase は、ISDB-Tmm のファイルキャスティングの誤り訂正(消失訂正)に利用可能です。ISDB-Tmm については、以下の URL にまとめました。

http://sakaiyas.cocolog-nifty.com/nikki/isdbtmm.html

----【2010年03月27日 追記】(ここまで)----

参考資料

RFC5170 Low Density Parity Check (LDPC) Staircase and Triangle Forward Error Correction (FEC) Schemes
RFC5052 Forward Error Correction (FEC) Building Block
RFC3450 Asynchronous Layered Coding (ALC) Protocol Instantiation
RFC3926 FLUTE - File Delivery over Unidirectional Transport

「誤り検出訂正」ではなく「欠損部分の修復」ということである。

 「LDPC」で Web検索を行なうと、受信したデータが正しいかどうかチェックし、それを修復する場合の例をよく見かける(それ自体は LDPC で行なえるので間違いというわけではない)。
RFC5170 の場合は、「修復用データを用いて受信できなかった部分を修復する(作り出す)」、消失訂正 と理解すればよい。

 1対多(受信者が多数の意味)で送受信する場合、受信者の状況により受信できなかった部分が異なる。どの部分が欠損しても修復できるようにしたものが LDPC である。

シンボルとブロックについて

 ファイルを E バイト単位のシンボルに分け、さらにシンボルを k 個束ねて1ブロックを形成するということである。以下に例を示す。

B = 10 シンボル数 (ブロックの限界サイズ)
L = 92 バイト (ファイルサイズ)
E = 4 バイト (シンボル長)

のとき、

T = CEIL( L / E ) = 23 シンボル数 (全シンボル数)
N = CEIL( T / B ) = 3 ブロック数 (全ブロック数)

k = A_large = CEIL( T / N ) = 8 シンボル数 (前半ブロック)
k'= A_small = FLOOR( T / N ) = 7 シンボル数 (後半ブロック)
I = T - A_small * N = 2 ブロック数 (前半ブロック数)

となる(CEIL は切上げ、FLOOR は切捨て関数)。

上記の例では、『□』を E バイトのシンボルとすると

□□□□□□□□ ・・・ 1ブロック目 (A_large)
□□□□□□□□ ・・・ 2ブロック目 (A_large)
□□□□□□□ ・・・・ 3ブロック目 (A_small)

とファイルが分割される。
このような分割方法を用いる理由は、単純に B 個ごとに分割すると、

□□□□□□□□□□ ・・・ 1ブロック目
□□□□□□□□□□ ・・・ 2ブロック目
□□□ ・・・・・・・・・・ 3ブロック目

と最終ブロックのシンボル数が小さくなった場合、パリティチェック行列も小さくなり、修復しづらくなるためである。

max_n と修復シンボルについて

上記の例に引き続き、

max_n = 20 シンボル数 (修復シンボルを含めたブロックの限界サイズ)

とすると、

n = FLOOR( k * max_n / B ) = 16
n'= FLOOR( k'* max_n / B ) = 14

となる。

k (A_large) の場合は、(n-k) 行×n 列 のパリティチェック行列となる。
k'(A_small) の場合は、(n'-k') 行×n'列 のパリティチェック行列となる。

上記の例では、『□』を E バイトのソースシンボルとし、『■』を E バイトの修復シンボルとすると、

□□□□□□□□■■■■■■■■ ・・・ 1ブロック目 (A_large)
□□□□□□□□■■■■■■■■ ・・・ 2ブロック目 (A_large)
□□□□□□□■■■■■■■ ・・・・・ 3ブロック目 (A_small)

と分割される(ソースシンボルとはファイル内容そのものである)。

パリティチェック行列(LDPC Staircase の場合の例)

1 1 0 1 1 0 0 0
1 0 1 1 1 1 0 0
1 1 1 0 0 1 1 0
0 1 1 1 0 0 1 1

(n - k) 行 n 列の行列となる。
上記のパリティチェック行列では、説明の簡素化のため、 k = 4, n = 8 としている。

・左行列(ソースシンボル側) ・・・ 列数 k 個

1 1 0 1
1 0 1 1
1 1 1 0
0 1 1 1

実際の LDPC Staircase では、(一部の)擬似乱数の性質である seed 値が同じ場合、擬似乱数列も同じとなる性質を逆利用して、左行列データではなく、受信者に seed 値だけ渡すようにしている。

・右行列(修復シンボル側) ・・・ 列数 (n - k) 個

     1 0 0 0
     1 1 0 0
     0 1 1 0
     0 0 1 1

この右行列の右上部分が全て 0 なので、生成行列を作成することなく、パリティチェック行列を使って修復シンボルを以下のように計算できる。

・ソースシンボル(例)

0x01, 0x02, 0x03, .., 0x0F, 0x10

E = 4 バイト として、以下のように並べなおす。

0x01 0x05 0x09 0x0D
0x02 0x06 0x0A 0x0E
0x03 0x07 0x0B 0x0F
0x04 0x08 0x0C 0x10

・1行目の計算(5列目の修復シンボルを求める)

1 1 0 1 1 0 0 0

0x01 xor 0x05 xor 0x0D = 0x09
0x02 xor 0x06 xor 0x0E = 0x0A
0x03 xor 0x07 xor 0x0F = 0x0B
0x04 xor 0x08 xor 0x10 = 0x1C

上記のように、『1』とビットの立っている列のシンボルを xor (排他的論理和) して、修復シンボルを求めている(以下同様)。

・2行目の計算(6列目の修復シンボルを求める)

1 0 1 1 1 1 0 0

0x01 xor 0x09 xor 0x0D xor 0x09 = 0x0C
0x02 xor 0x0A xor 0x0E xor 0x0A = 0x0C
0x03 xor 0x0B xor 0x0F xor 0x0B = 0x0C
0x04 xor 0x0C xor 0x10 xor 0x1C = 0x04

・3行目の計算(7列目の修復シンボルを求める)

1 1 1 0 0 1 1 0

0x01 xor 0x05 xor 0x09 xor 0x0C = 0x01
0x02 xor 0x06 xor 0x0A xor 0x0C = 0x02
0x03 xor 0x07 xor 0x0B xor 0x0C = 0x03
0x04 xor 0x08 xor 0x0C xor 0x04 = 0x04

・4行目の計算(8列目の修復シンボルを求める)

0 1 1 1 0 0 1 1

0x05 xor 0x09 xor 0x0D xor 0x01 = 0x00
0x06 xor 0x0A xor 0x0E xor 0x02 = 0x00
0x07 xor 0x0B xor 0x0F xor 0x03 = 0x00
0x08 xor 0x0C xor 0x10 xor 0x04 = 0x10

・ソースシンボルの後に修復シンボルを並べる

0x01 0x05 0x09 0x0D 0x09 0x0C 0x01 0x00
0x02 0x06 0x0A 0x0E 0x0A 0x0C 0x02 0x00
0x03 0x07 0x0B 0x0F 0x0B 0x0C 0x03 0x00
0x04 0x08 0x0C 0x10 0x1C 0x04 0x04 0x10

以下の1行単位( E = 4 )でデータを送ることになる。

0x01, 0x02, 0x03, 0x04
0x05, 0x06, 0x07, 0x08
0x09, 0x0A, 0x0B, 0x0C
0x0D, 0x0E, 0x0F, 0x10
 :
0x09, 0x0A, 0x0B, 0x1C
0x0C, 0x0C, 0x0C, 0x04
0x01, 0x02, 0x03, 0x04
0x00, 0x00, 0x00, 0x10
 :

ソースシンボルの修復例

1 1 0 1 1 0 0 0
1 0 1 1 1 1 0 0
1 1 1 0 0 1 1 0
0 1 1 1 0 0 1 1

上記のパリティチェック行列の2行目を利用して修復する。

1 0 1 1 1 1 0 0

1列目、3列目、5列目、6列目のデータを使って4列目のデータを修復する。

0x01 xor 0x09 xor 0x09 xor 0x0C = 0x0D
0x02 xor 0x0A xor 0x0A xor 0x0C = 0x0E
0x03 xor 0x0B xor 0x0B xor 0x0C = 0x0F
0x04 xor 0x0C xor 0x1C xor 0x04 = 0x10

修復シンボルの修復例

1 1 0 1 1 0 0 0
1 0 1 1 1 1 0 0
1 1 1 0 0 1 1 0
0 1 1 1 0 0 1 1

上記のパリティチェック行列の3行目を利用して修復する。

1 1 1 0 0 1 1 0

1列目、2列目、3列目、7列目のデータを使って6列目のデータを修復する。

0x01 xor 0x05 xor 0x09 xor 0x01 = 0x0C
0x02 xor 0x06 xor 0x0A xor 0x02 = 0x0C
0x03 xor 0x07 xor 0x0B xor 0x03 = 0x0C
0x04 xor 0x08 xor 0x0C xor 0x04 = 0x04

このように、ソースシンボルばかりでなく、修復シンボルも修復可能である。

以上

|

« ACE32のログ機能(画面入力編) | トップページ | ISDB-Tmm (携帯端末向けマルチメディア放送) »

コメント

補足説明ですが、パリティチェック行列から生成行列を作成する方法を以下に示します。

1 1 0 1 1 0 0 0
1 0 1 1 1 1 0 0
1 1 1 0 0 1 1 0
0 1 1 1 0 0 1 1

上記のパリティチェック行列(例)の右行列が単位行列(対角線のみ『1』)となるように、任意の行の値を xor (排他的論理和)していく。

1 1 0 1 1 0 0 0
1 0 1 1 1 1 0 0
1 1 1 0 0 1 1 0
0 1 1 1 0 0 1 1

    ↓ 2行目に1行目を xor する。

1 1 0 1 1 0 0 0
0 1 1 0 0 1 0 0
1 1 1 0 0 1 1 0
0 1 1 1 0 0 1 1

    ↓ 3行目に2行目を xor する。

1 1 0 1 1 0 0 0
0 1 1 0 0 1 0 0
1 0 0 0 0 0 1 0
0 1 1 1 0 0 1 1

    ↓ 4行目に3行目を xor する。

1 1 0 1 1 0 0 0
0 1 1 0 0 1 0 0
1 0 0 0 0 0 1 0
1 1 1 1 0 0 0 1

上記の行列が生成行列(正確には本文章の後半を参照のこと)となる。

・ソースシンボル(例)

0x01, 0x02, 0x03, .., 0x0F, 0x10

E = 4 バイト として、以下のように並べなおす。

0x01 0x05 0x09 0x0D
0x02 0x06 0x0A 0x0E
0x03 0x07 0x0B 0x0F
0x04 0x08 0x0C 0x10

・1行目の計算(5列目の修復シンボルを求める)

1 1 0 1 1 0 0 0

0x01 xor 0x05 xor 0x0D = 0x09
0x02 xor 0x06 xor 0x0E = 0x0A
0x03 xor 0x07 xor 0x0F = 0x0B
0x04 xor 0x08 xor 0x10 = 0x1C

・2行目の計算(6列目の修復シンボルを求める)

0 1 1 0 0 1 0 0

0x05 xor 0x09 = 0x0C
0x06 xor 0x0A = 0x0C
0x07 xor 0x0B = 0x0C
0x08 xor 0x0C = 0x04

・3行目の計算(7列目の修復シンボルを求める)

1 0 0 0 0 0 1 0

0x01 = 0x01
0x02 = 0x02
0x03 = 0x03
0x04 = 0x04

・4行目の計算(8列目の修復シンボルを求める)

1 1 1 1 0 0 0 1

0x01 xor 0x05 xor 0x09 xor 0x0D = 0x00
0x02 xor 0x06 xor 0x0A xor 0x0E = 0x00
0x03 xor 0x07 xor 0x0B xor 0x0F = 0x00
0x04 xor 0x08 xor 0x0C xor 0x10 = 0x10

・ソースシンボルの後に修復シンボルを並べる

0x01 0x05 0x09 0x0D 0x09 0x0C 0x01 0x00
0x02 0x06 0x0A 0x0E 0x0A 0x0C 0x02 0x00
0x03 0x07 0x0B 0x0F 0x0B 0x0C 0x03 0x00
0x04 0x08 0x0C 0x10 0x1C 0x04 0x04 0x10

このように、ブログの本文で書いた結果と同じになる。

・生成行列について

 生成行列を上記では、

1 1 0 1 1 0 0 0
0 1 1 0 0 1 0 0
1 0 0 0 0 0 1 0
1 1 1 1 0 0 0 1

と (n - k) 行× n 列の行列にしたが、数学的に正確に表現すると、以下のように k 行× n 列 の行列となる。

1 0 0 0 1 0 1 1
0 1 0 0 1 1 0 1
0 0 1 0 0 1 0 1
0 0 0 1 1 0 0 1

上記の左行列は k 行 k 列の単位行列で、右行列は k 行 (n - k) 列の行列で1つ上の計算に使った方の生成行列の (n - k) 行 k 列の左行列の転置行列である。
k 個のソースシンボルを 1 行 k 列の行ベクトルにし、生成行列を右から掛ける、ということである。

以上

投稿: 本人 | 2010年3月12日 (金) 10:22

RFC5170 に載っているプログラムコードを参考にして、LDPC Staircase のパリティチェック行列を表示する Excel ファイルを作成しました。

http://sakaiyas.cocolog-nifty.com/nikki/files/work/rfc5170_staircase.xls

seed, N1(左行列の各列の『1』の個数), k, n に値を入力して、<計算開始> ボタンをクリックすると、パリティチェック行列(パリティ検査行列)が表示されます。

投稿: 本人 | 2010年5月 6日 (木) 02:43

RFC5170 に載っているプログラムコードを参考にして、LDPC Staircase のパリティチェック行列を表示する Excel ファイルを作成しました。
→ グループ化(G>1)のプログラムコードを追加しました。

http://sakaiyas.cocolog-nifty.com/nikki/files/work/rfc5170_staircase_g.xls

seed, N1(左行列の各列の『1』の個数), G(1パケット内のシンボル数), k, n に値を入力して、<計算開始> ボタンをクリックすると、パリティチェック行列(パリティ検査行列)と ESI(Encoding Symbol ID)数列が表示されます。
→ ESI には ESI 数列の一番左の数値を入力願います(受信側のプログラムコードによる検算用です)。

投稿: 本人 | 2010年5月 6日 (木) 17:43

RFC5170 で使用する「PM88」の擬似乱数について、以下に解説しています。

http://sakaiyas.cocolog-nifty.com/nikki/ashiato.html#comment-47918247

seed 値とは、乱数の種(たね)のことで、PM88 の場合は、同じ seed 値を与えると、同一の擬似乱数列となります。

投稿: 本人 | 2010年5月 7日 (金) 09:36

「LDPC Triangle」版の Excel ファイルも作成してみました。

RFC5170 に載っているプログラムコードを参考にして、LDPC Triangle のパリティチェック行列を表示する Excel ファイルを作成しました。
→ グループ化(G>1)のプログラムコードを追加しました。
→ LDPC Triangle 版です。

http://sakaiyas.cocolog-nifty.com/nikki/files/work/rfc5170_triangle_g.xls

seed, N1(左行列の各列の『1』の個数), G(1パケット内のシンボル数), k, n に値を入力して、<計算開始> ボタンをクリックすると、パリティチェック行列(パリティ検査行列)と ESI(Encoding Symbol ID)数列が表示されます。
→ ESI には ESI 数列の一番左の数値を入力願います(受信側のプログラムコードによる検算用です)。
→ グループ化(G>1)の場合、LDPC Staircase の修復シンボルの ESI 数列と異なるものになります。

投稿: 本人 | 2010年5月 7日 (金) 14:08

以下は、Excel ファイル(『rfc5170_staircase_g.xls』や『rfc5170_triangle_g.xls』) の VBA コードに追加する形の、LDPC Staircase と LDPC Triangle 共通の符号化(Encoding)となる、修復シンボルの計算例です。

┌── 修復シンボルの計算例(ここから) ──

│Dim iSymbol(MAX_N) As Long

│' ソースシンボル「iSymbol(0) ~ iSymbol(k-1)」には、
│' 既に値が入っているものとする。
│' 実際は Long 型ではなく、Byte 型の2次元配列等になる。


│  ' 以下は、main_func() 内に記述する。

│  Dim repair As Long

│  ' 修復シンボル「iSymbol(k) ~ iSymbol(n-1)」の計算例
│  ' (パリティチェック行列の計算後に記述する)

│  For i = k To n - 1
│    repair = 0
│    For j = 0 To i - 1
│      If iH(i - k, j) <> 0 Then
│        repair = repair Xor iSymbol(j)
│      End If
│    Next j
│    iSymbol(i) = repair
│  Next i

└── 修復シンボルの計算例(ここまで) ──

以上

投稿: 本人 | 2010年5月 8日 (土) 18:22

http://planete-bcast.inrialpes.fr/ からダウンロードできる C++ の LDPC Staircase / Triangle の復号(Decode)プログラムでは、再帰呼出の構造なので、コールスタックサイズがシンボル数(正確にはパリティチェック行列の行数)に比例して膨大になります。スタックサイズをあまり大きくとることができない SymbianOS 等の環境では、スタックオーバーフローの危険性があるため、絶対にスタックオーバーフローにならず、かつ復号の高速性は維持するロジックに改変する必要があります。
ちなみに、符号化(Encode)の場合は、スタックオーバーフローの危険性を意識する必要は、ありません。

投稿: 本人 | 2010年11月18日 (木) 11:54

RFC3926( http://www.ietf.org/rfc/rfc3926.txt )の「5.1.2.1. FEC Encoding IDs 0, 128, and 130」にある Encoding Symbol Length(『E』:シンボル長)の説明によると、1つのオブジェクト(ファイル)に対して、シンボル長「E」は全て同一である必要があります(MUST条件)。
ファイルサイズ「L」(バイト)がシンボル長「E」(バイト)で割り切れない場合は、符号化・復号の計算時には、最終ソースシンボルにゼロを追加して E バイトにする必要があります(MUST条件)。
送信時に、最終ソースシンボルにゼロを追加して E バイトにするのは必須ではなく、送信者の意思・仕様によっては、ヘッダの Encoding Symbol Length フィールドに、最終ソースシンボルのみ E 未満の値が入る場合もあるということです。
 必然的に受信者は、ファイルサイズ「L」がシンボル長「E」で割り切れない場合は、最終ソースシンボルにゼロを追加して E バイトになっているのか、E バイトより短い最終ソースシンボルそのもので送られてきたのか、判断し どちらも受け付ける実装になります。

投稿: 本人 | 2010年11月28日 (日) 21:31

素人の質問ですみません.
修復する際に2行目や3行目を利用するのはなぜでしょうか?
4列目や6列目が誤っているということが既知なのでしょうか?

投稿: 電匠 | 2011年1月 9日 (日) 10:27

電匠 様

 素人の質問も大歓迎です。

> 修復する際に2行目や3行目を利用するのはなぜでしょうか?
> 4列目や6列目が誤っているということが既知なのでしょうか?

RFC5170 には、はっきり書いていないのですが、以下の前提条件があります。

==== 前提条件(ここから) ====
(1) 受信シンボルが正しいか否かは、LDPC では判断しない。

 例えば、ISDB-Tmm の場合には、シンボルをカプセル化した ULE(RFC4326) にある CRC-32 で受信シンボルが正しいか否かをチェックします。
 チェック済みの正しい受信シンボルを、常に LDPCの復号ロジックに渡す、ということです。

(2) シンボルを1つ受信したときに、毎回 復号を試みる。

(3) 既に受信もしくは復号済みのシンボルを受信したときは、復号処理を行わない。

(4) ソースシンボルも修復シンボルも順番に受信するわけではない。

 例えば、ISDB-Tmm では、シンボルをランダムにインタリーブして、順番を変えソースシンボルと修復シンボルを間引くことになります。

(5) RFC5170 の復号は、受信していないシンボルの復号を行うものである。

 正確には、受信に失敗したシンボルも含みます。
==== 前提条件(ここまで) ====

 私のブログの本文にある「ソースシンボルの修復例」では、例えば、1列目、3列目、5列目に該当するシンボルを正常に受信し、6列目に該当するシンボルを正常に受信したと考えてください。
その際、パリティチェック行列の2行目を使うと、4列目に該当するシンボルを復号できる、ということです。
どの行が復号に使えるのかは、『1』とビットが立っている列で不明な該当シンボルが残り1つである行をサーチするわけです。
 「修復シンボルの修復例」では、例えば、1列目、2列目、3列目に該当するシンボルを正常に受信し、7列目に該当するシンボルを正常に受信したと考えてください。
その際、パリティチェック行列の3行目を使うと、6列目に該当するシンボルを復号できる、ということです。
「ソースシンボルの修復例」と「修復シンボルの修復例」は、それぞれ独立していると考えてください。

 蛇足ですが、実際の復号処理では、復号されたシンボルを新たな受信シンボルと考え、パリティチェック行列の『1』とビットが立っている列で不明な該当シンボルが残り1つである行をサーチし、再帰的(連鎖的)に復号処理を行います。
詳細は http://planete-bcast.inrialpes.fr/ からダウンロードできる C++ の復号プログラム( ldpc_v2.1_src.zip 内の ldpc_fec_iterative_decoding.cpp 等)を参照願います。まあ、左行列と右行列が RFC5170 とは左右逆になっているので、その点は注意願います。

以上

投稿: 本人 | 2011年1月10日 (月) 00:05

電匠です.happy01
ありがとうございます.
消失した部分を修復するということですね.

>「ソースシンボルの修復例」と「修復シンボルの修復例」は、それぞれ独立していると考えてください。

修復する時には特にソースとパリティを区別しなくてもよいように思いますが、独立というのは別々の処理という意味でしょうか.


投稿: 電匠 | 2011年1月10日 (月) 11:45

> 修復する時には特にソースとパリティを区別しなくてもよいように思いますが、独立というのは別々の処理という意味でしょうか.

 修復時にソースとパリティのシンボルを区別しない、という考えで合っています。
非常に細かいことを言うと、全ソースシンボルの復号完了時に、ソースシンボル用にメモリ確保した領域を維持したままにし、修復(パリティ)シンボルはメモリ開放する、という違いがロジックによっては、あったりします。

 独立と書いたのは、単に「ソースシンボルの修復例」で受信したシンボルを維持したまま、次に「修復シンボルの修復例」のシンボルを受信する、という勘違いをしないために、無関係(independent)という意味で書いただけです。

以上

投稿: 本人 | 2011年1月10日 (月) 12:25

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/42597/47765991

この記事へのトラックバック一覧です: LDPC Staircase の勘どころメモ:

« ACE32のログ機能(画面入力編) | トップページ | ISDB-Tmm (携帯端末向けマルチメディア放送) »