インターリーブインターリーブの概要

主に以下のような用途がある。

誤り検出訂正に使う。特にデータ転送、ディスク・ストレージ、記憶装置など。
共通の媒体への複数の入力の多重化に使う。電気通信では動的帯域割当機構を通して実装され、特にQOSやレイテンシの問題解決に使う。ストリーミング用途では、映像と音など複数の入力ストリームを擬似的に同時に受信することを可能にする。
コンピュータの記憶装置のアクセス性能を向上させるのに使う。例えば、ディスク・ストレージでの不連続な領域使用、メモリのインターリーブ、メモリ割り当て戦略の一種であるページ・カラーリング技法などがある。

ディスク・ストレージでのインターリーブ

歴史的には、フロッピーディスクやハードディスクなどのディスクを使ったストレージ・デバイスでのブロックの配置にインターリーブを使っていた。インターリーブの第一の目的は、コンピュータがデータ転送可能となるタイミングとディスクドライブのヘッドが当該ブロック上に到達して実際にデータを読み出せるようになるタイミングを合わせることだった。1990年代より以前にはこのようなインターリーブが非常に一般的だったが、処理速度の向上に伴って徐々に廃れていった。2012年現在のディスク・ストレージでは、もはやインターリーブは使われていない。

インターリーブでは、セクタを読んだ後の処理時間を考慮して、コンピュータが次のセクタを読む用意ができたときにちょうどそのセクタ上にヘッドが来るように配置する。従って、処理速度とインターリーブされたセクタの配置が一致していればデータ転送を高速化できるが、一致していないと著しく性能を低下させることがある。

例

ディスクの構造。
(A) トラック
(B) （幾何学的）セクタ
(C) トラックセクタ
(D) クラスタ

ディスク・ストレージ上の情報は、セクタまたはブロックと呼ばれる非常に小さな部分に分割して格納されている。そして各ディスク表面のトラックと呼ばれる同心円状の領域に配置される。ブロックをトラック上に順に配置するのが最も簡単だが、初期の記憶装置ではそのような配置は実用的ではなかった。

書き込むあるいは読み出すデータは、メモリ上のバッファと呼ばれる特別な領域に置かれる。データを書き込む場合、まずデータをバッファに移し、バッファからディスクに書き込む。データを読み出す場合はその逆で、まずディスクからバッファにデータを転送し、バッファからそのデータを必要とする場所に移す。初期のコンピュータで1つのセクタを読み出す動作は十分高速でないことが多かったため、連続して一連のセクタを読み出す場合、あるセクタを読み出してから次のセクタを読み出すためにバッファが使用可能になるまで時間がかかった。

セクタを物理的に連続に配置すると、1つ目のセクタを読み出すのに時間を要してしまい、次のセクタを読み出す準備ができたときにはディスクの回転によってヘッドが例えば4セクタ先（5番目）まで移動済みということになる。すると次のセクタを読み出すためには、ディスクが1回転して2番目のセクタがヘッドの位置に来るまで待たなければならない。1周（幾何学的セクタ）に1から9までのセクタがあるとすると、6、7、8、9、1 というセクタをやり過ごすことになる。そのため余分な待ち時間が発生し、データ転送レートが低下する。

この処理遅延をなんとかするには、このシステムでの理想的インターリーブは 1:4 となり、セクタ配置は 1 8 6 4 2 9 7 5 3 のようになる。セクタ1を読み出すと、処理を行っている間に 8 6 4 という3セクタを通り過ぎ、コンピュータが再び読み出し動作可能となったときセクタ2がちょうどヘッド位置に来ることになる。

より具体的な例としては、1トラック26セクタの8インチフロッピディスクを外部記憶媒体として使用していたPC-9801にて、フロッピディスクをインターリーブ 1:2 とした場合、セクタ配置は 1 14 2 15 3 16 ... 25 12 26 13 1 のようになる。このようにした場合、インターリーブ 1:1 の場合に、640x400ドットの画面をロードするのに70秒かかっていたのに対し、1:2 とした場合ロード時間が7秒に短縮されている^[1]。

インターリーブのことを "skip factor" と呼ぶこともあり^[2]^[3]、連続な論理セクタの間の物理セクタの数を意味する。skip factor が0ならば、セクタは 1 2 3 4 5 6 …… のように順に配置される。

2012年現在のディスク・ストレージでは、バッファ領域がかなり大きくとられているため、インターリーブは不要である。今ではセクタをグループ化したクラスタ単位でデータを格納することが多く、1ブロックを構成する全セクタを格納するのに十分なバッファを備えている。

誤り訂正符号でのインターリーブ

インターリーブは、デジタル通信やストレージシステムの前方誤り訂正の性能向上のために使われることも多い。多くの伝送路は無記憶 (memoryless) ではない。誤りは散発的（ランダム）ではなく、ある時点で集中して起きるのが一般的である（バースト誤り）。1つの符号語内で複数の誤りが発生して誤り訂正符号の能力を超えると、元の符号語を復元できなくなる。この場合のインターリーブは、複数の符号語について、それを構成する情報源シンボルをシャッフルし、この問題を改善する。そのため、誤りの分布がより一様になる^[4]。

ターボ符号やLDPC符号などの現代的な繰り返し符号の解析によると、それらは誤りが独立に分布することを仮定していることが多い^[5]。従ってLDPC符号を使ったシステムは、それに加えて符号語内のシンボル群をまたがったインターリーブを施すのが一般的である^[6]。

ターボ符号ではインターリーバが必須の構成要素であり、インターリーバの設計が全体の性能に大きく影響する^[4]^[7]。その反復復号アルゴリズムは、復号器を表す因子グラフに短いサイクルがない場合に最もうまく働く。そのためインターリーバは短いサイクルを防ぐよう選択される。

インターリーバの設計には次のようなものがある。

矩形（または一様）インターリーバ（上述の skip factor を使った手法に似ている）
畳み込みインターリーバ
ランダムインターリーバ（この場合のインターリーバは既知の無作為順列）
S-ランダムインターリーバ（この場合のインターリーバは既知の無作為順列で、距離S内の入力シンボルが出力で距離S内に出現しないよう配置するという制限がある）^[8]
衝突のない二次順列多項式 (QPP)^[9]（例えば LTE無線通信規格で使用）^[10]

複数搬送波による通信システムでは、搬送波間でインターリーブを追加することで信号や少数の搬送波でのノイズの効果を和らげることがある（例えば、OFDMにおける周波数選択性フェージング）^[11]。

例

インターリーブしない場合:

aaaabbbbccccddddeeeeffffgggg                 :元のメッセージ
aaaabbbbcccc____eeeeffffgggg                 :転送時にバースト誤りが生じた結果

符号語 dddd が誤りによって受信できないため、復号できないか間違った復号になる。

インターリーブした場合:

aaaabbbbccccddddeeeeffffgggg                 :元のメッセージ
abcdefgabcdefgabcdefgabcdefg                 :インターリーブされたメッセージ
abcdefgabcd____bcdefgabcdefg                 :転送時にバースト誤りが生じた結果
aa_abbbbccccdddde_eef_ffg_gg                 :デインターリーブ後の受信メッセージ

aaaa、eeee、ffff、gggg という符号語それぞれで1ビットのみ変化しているので、1ビット誤り訂正符号によって全てを正しく復号できる。

インターリーブしない場合:

ThisIsAnExampleOfInterleaving                :元の送信文
ThisIs______pleOfInterleaving                :転送時にバースト誤りが生じた結果

"AnExample" という部分がほとんど推測できない状態であり、訂正が困難である。

インターリーブした場合:

ThisIsAnExampleOfInterleaving...             :元の送信文
TIEpfeaghsxlIrv.iAaenli.snmOten.             :インターリーブされた送信文
TIEpfe______Irv.iAaenli.snmOten.             :転送時にバースト誤りが生じた結果
T_isI_AnE_amp_eOfInterle_vin_...             :デインターリーブ後の受信文

どの単語も完全には失われておらず、失われた文字は最小限の推測で復元可能である。

インターリーブの欠点

インターリーブを使う場合、レイテンシが問題となる。これは、パケットを復号するに際して、インターリーブされたブロック全体を受信してからでないと復号を開始できないためである^[12]。また、インターリーバは誤り群の構造を隠蔽してしまう。インターリーバがない場合、誤り群の構造を利用できるさらに進んだ復号アルゴリズムを使うことができ、復号器とインターリーバを組合わせた単純な構成よりも信頼性の高い通信が達成できる。

脚注・出典

^ 浅野泰之、壁谷正洋、金磯善博、桑野雅彦『PC-9801システム解析(下)』アスキー、1983年12月1日、102-103頁。ISBN 4-87148-715-6。
^ "Function Requests Specification"
^ "Disk ’skip factor’ explained"
^ ^a ^b B. Vucetic, J. Yuan (2000), Turbo codes: principles and applications, Springer Verlag, ISBN 978-0792378686
^ M. Luby, M. Mitzenmacher, A. Shokrollahi, D. Spielman, V. Stemann (1997), “Practical Loss-Resilient Codes”, Proc. 29th annual Association for Computing Machinery (ACM) symposium on Theory of computation
^ “Digital Video Broadcast (DVB); Second generation framing structure, channel coding and modulation systems for Broadcasting, Interactive Services, News Gathering and other satellite broadband applications (DVB-S2)”, En 302 307 (ETSI) (V1.2.1), (April 2009)
^ K. Andrews et al. (November 2007), “The Development of Turbo and LDPC Codes for Deep-Space Applications”, Proc. of the IEEE 95 (11)
^ S. Dolinar and D. Divsalar. Weight Distributions for Turbo Codes Using Random and Nonrandom Permutations. 1995. PDFダウンロード
^ Takeshita, Oscar (2006). "Permutation Polynomial Interleavers: An Algebraic-Geometric Perspective". arXiv:cs/0601048。
^ 3GPP TS 36.212, version 8.8.0, page 14
^ “Digital Video Broadcast (DVB); Frame structure, channel coding and modulation for a second generation digital terrestrial television broadcasting system (DVB-T2)”, En 302 755 (ETSI) (V1.1.1), (September 2009)
^ “Explaining Interleaving - TechGeeks Online”. techgeeks-online.com. 2010年6月3日閲覧。

[前の解説]

[続きの解説]

「インターリーブ」の続きの解説一覧

[1] 浅野泰之、壁谷正洋、金磯善博、桑野雅彦『PC-9801システム解析(下)』アスキー、1983年12月1日、102-103頁。ISBN 4-87148-715-6。

[2] "Function Requests Specification"

[3] "Disk ’skip factor’ explained"

[turbo-principles-4] B. Vucetic, J. Yuan (2000), Turbo codes: principles and applications, Springer Verlag, ISBN 978-0792378686

[5] M. Luby, M. Mitzenmacher, A. Shokrollahi, D. Spielman, V. Stemann (1997), “Practical Loss-Resilient Codes”, Proc. 29th annual Association for Computing Machinery (ACM) symposium on Theory of computation

[6] “Digital Video Broadcast (DVB); Second generation framing structure, channel coding and modulation systems for Broadcasting, Interactive Services, News Gathering and other satellite broadband applications (DVB-S2)”, En 302 307 (ETSI) (V1.2.1), (April 2009)

[7] K. Andrews et al. (November 2007), “The Development of Turbo and LDPC Codes for Deep-Space Applications”, Proc. of the IEEE 95 (11)

[8] S. Dolinar and D. Divsalar. Weight Distributions for Turbo Codes Using Random and Nonrandom Permutations. 1995. PDFダウンロード

[Takeshita1-9] Takeshita, Oscar (2006). "Permutation Polynomial Interleavers: An Algebraic-Geometric Perspective". arXiv:cs/0601048。

[10] 3GPP TS 36.212, version 8.8.0, page 14

[11] “Digital Video Broadcast (DVB); Frame structure, channel coding and modulation for a second generation digital terrestrial television broadcasting system (DVB-T2)”, En 302 755 (ETSI) (V1.1.1), (September 2009)

[12] “Explaining Interleaving - TechGeeks Online”. techgeeks-online.com. 2010年6月3日閲覧。

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

インターリーブ インターリーブの概要