« 2010年1月 | トップページ | 2010年4月 »

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

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

以上

| | コメント (12) | トラックバック (0)

« 2010年1月 | トップページ | 2010年4月 »