インターリーブ

インターリーブまたはインターリービング（英: Interleaving）は計算機科学と電気通信において、データを何らかの領域（空間、時間、周波数など）で不連続な形で配置し、性能を向上させる技法を指す。

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

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

[編集]

歴史的には、フロッピーディスクやハードディスクなどのディスクを使ったストレージ・デバイスでのブロックの配置にインターリーブを使っていた。インターリーブの第一の目的は、コンピュータがデータ転送可能となるタイミングとディスクドライブのヘッドが当該ブロック上に到達して実際にデータを読み出せるようになるタイミングを合わせることだった。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]。また、インターリーバは誤り群の構造を隠蔽してしまう。インターリーバがない場合、誤り群の構造を利用できるさらに進んだ復号アルゴリズムを使うことができ、復号器とインターリーバを組合わせた単純な構成よりも信頼性の高い通信が達成できる。

カラーテレビ信号でのインターリーブ

[編集]

インターリーブは、白黒テレビの白黒信号(輝度信号)に干渉せずに、いかにして色副搬送波（カラーサブキャリア）を多重するかで考えられた方法である。

輝度信号を周波数領域に展開しそのスペクトル分布と、輝度信号を原点として色副搬送波を約3.579545MHz上に多重すると色副搬送波のスペクトル分布が、髪の毛を整える櫛を一本違いで重ねるような分布となる。そうすることによって両信号の干渉を防ぐ事が可能となる。なお、色副搬送波が上記のような中途半端な数になるのには理由がある。NTSC方式が開発された当時は、振幅変調である輝度信号を基本として、その4.5MHz上に音声副搬送波が多重されていて、復調方式としてテレビジョン受像機を安価に製造するためにインターキャリア方式が用いられていた。輝度信号から相対的に4.5MHz上に音声副搬送波が周波数変調で多重されているのでインターキャリア方式の受像機では音声が人間の耳の特性上、無視できない歪率を持つことになる。これを動かすことができなかったため、仕方なく、垂直同期周波数を約59.94Hzまで下げ、白黒受像機で引き込めるかどうかのフィールドチェックが行われた。そして、引き込める事が解り、実用化された経緯がある。現在では音声復調にはセパレートキャリア方式が用いられている。白黒テレビに音声を周波数変調で多重し、そして色副搬送波を位相変調で多重するために、考え抜かれた方式である。アナウンサーがギンガムチェックのような細かい模様の服を着ないのは、輝度信号の周波数分布が高い方向にスペクトルが立つため、カラー信号との干渉で、虹色のような色が流れるようについてしまうためである。これをカラー妨害という。

脚注・出典

[編集]
  1. ^ 浅野泰之、壁谷正洋、金磯善博、桑野雅彦『PC-9801システム解析(下)』アスキー、1983年12月1日、102-103頁。ISBN 4-87148-715-6。 
  2. ^ "Function Requests Specification"
  3. ^ "Disk ’skip factor’ explained"
  4. ^ a b 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ダウンロード
  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日閲覧。

関連項目

[編集]

外部リンク

[編集]
「https://ja.wikipedia.org/w/index.php?title=インターリーブ&oldid=102267430」から取得