(57)【要約】  メモリを仕切って、絶えずスライドするFIFOに分割し得る。各FIFOは、メモリ中に縦列に積層して、最も古いデータをベースオフセットに、また、最新データを末尾に（又は反対に）配置し得る。各符号、ポインタは、適切な量(通常、先行の符号の場合よりJ以上)だけ(組サイズを法として)インクリメントし得る。各組の後、ポインタを先行のインクリメントよりJ以上だけインクリメントして、プロセスが始まり、メモリの末尾に到達すると、メモリを折り返し得る。予め設定された数の符号に達した後、プロセスは、インクリメントJから再開し得る。他の選択肢として、ポインタは、インクリメントよりもむしろデクリメントし得る。従って、最新符号は、現在のFIFOにおける最も古い符号が明け渡したメモリ位置を割り込んで利用し、FIFOをスライドさせ、誤り訂正コードインターリーブ処理のために、極めて効率的で信頼性のあるメモリの使用方法を提供する。【特許請求の範囲】
【請求項１】
I個の符号が一組になっている誤り訂正コードの符号をインターリーブするための方法であって、
Jを遅延値とすると、サイズI(I-1)*J/2+1のメモリ中の初期位置にプレースホルダを設定する段階、が含まれ、
I個の受信符号毎に、
0のステップからI-1のステップまで反復的に計数し、次の段階、即ち、
a)書込みポインタを前記プレースホルダに等しく設定する段階と、
b)ステップが0である場合、前記プレースホルダを読出しポインタに等しく設定する段階と、
c)ステップが0でない場合、前記プレースホルダをステップ*Jメモリ位置進ませる段階であって、前記プレースホルダ値が前記メモリの末尾を過ぎた場合、折り返す前記段階と、
d)前記読出しポインタを前記プレースホルダに等しく設定する段階と、
e)前記読出しポインタによって示される前記メモリ中の位置から読出す段階と、
f)前記書込みポインタによって示される前記メモリ中の位置に前記I個の符号における次の符号を書込む段階であって、ステップが0でなければ、この場合、バイパスされる前記段階と、
を実施する方法。
【請求項２】
請求項1に記載の方法であって、
前記プレースホルダを進ませる前記段階には、前記メモリサイズを法として、ステップ*Jを前記プレースホルダに加算する段階が含まれる方法。
【請求項３】
請求項1に記載の方法であって、
前記プレースホルダを進ませる前記段階には、前記メモリサイズを法として、ステップ*Jを前記プレースホルダから減算する段階が含まれる方法。
【請求項４】
請求項1に記載の方法であって、
符号が、それを遅延無しで送信することによってバイパスされる方法。
【請求項５】
I個の符号が一組になっている誤り訂正コードの符号をインターリーブするための方法であって、
Jを遅延値とすると、サイズI(I-1)*J/2+I+1のメモリ中の初期位置に書込みポインタを設定する段階、が含まれ、
I個の受信符号毎に、
0のステップからI-1のステップまで反復的に計数し、次の段階、即ち、
a)読出しポインタを前記書込みポインタの１メモリ位置後ろに等しく設定する段階であって、前記読出しポインタが前記メモリの末尾を過ぎた場合、折り返す前記段階と、
b)前記読出しポインタによって示される前記メモリ中の位置から読出す段階と、
c)前記書込みポインタによって示される前記メモリ中の位置に前記I個の符号における次の符号を書込む段階と、
d)前記書込みポインタを(ステップ+1)*Jメモリ位置進ませる段階であって、前記書込みポインタが前記メモリの末尾を過ぎた場合、折り返す前記段階と、
を実施する方法。
【請求項６】
請求項5に記載の方法であって、
前記書込みポインタを進ませる前記段階には、前記メモリサイズを法として、ステップ*Jを前記書込みポインタに加算する段階が含まれる方法。
【請求項７】
請求項5に記載の方法であって、
前記書込みポインタを進ませる前記段階には、前記メモリサイズを法として、前記書込みポインタからステップ*Jを減算する段階が含まれる方法。
【請求項８】
請求項5に記載の方法であって、
１メモリ位置後ろは、１メモリ位置小さいに等しい方法。
【請求項９】
請求項5に記載の方法であって、
１メモリ位置後ろは、１メモリ位置大きいに等しい方法。
【請求項１０】
I個の符号が一組になっている誤り訂正コードの符号をインターリーブするための方法であって、
Jを遅延値とすると、サイズI(I-1)*J/2+I+1のメモリ中の初期位置に書込みポインタを設定する段階、が含まれ、
I個の受信符号毎に、
0のステップからI-1のステップまで反復的に計数し、次の段階、即ち、
a)前記書込みポインタの１メモリ位置後ろにある前記メモリ中の位置から読出す段階であって、前記位置が前記メモリの末尾を過ぎた場合、折り返す前記段階と、
c)前記書込みポインタによって示される前記メモリ中の位置に前記I個の符号における次の符号を書込む段階と、
d)前記書込みポインタを(ステップ+1)*Jメモリ位置進ませる段階であって、前記書込みポインタが前記メモリの末尾を過ぎた場合、折り返す前記段階と、
を実施する方法。
【請求項１１】
請求項10に記載の方法であって、
前記書込みポインタを進ませる前記段階には、前記メモリサイズを法として、ステップ*Jを前記書込みポインタに加算する段階が含まれる方法。
【請求項１２】
請求項10に記載の方法であって、
前記書込みポインタを進ませる前記段階には、前記メモリサイズを法として、前記書込みポインタからステップ*Jを減算する段階が含まれる方法。
【請求項１３】
請求項10に記載の方法であって、
１メモリ位置後ろは、１メモリ位置小さいに等しい方法。
【請求項１４】
請求項10に記載の方法であって、
１メモリ位置後ろは、１メモリ位置大きいに等しい方法。
【請求項１５】
I個の符号が一組になっている誤り訂正コードの符号をインターリーブするための装置であって、
メモリと、
前記メモリに接続されたメモリイニシャライザと、
前記メモリに接続されたプレースホルダセッタと、
前記プレースホルダセッタに接続されたステップ反復カウンタと、
前記メモリ及び前記ステップ反復カウンタに接続された書込みポインタセッタと、
前記メモリ及び前記ステップ反復カウンタに接続された読出しポインタセッタと、
前記メモリ及び前記ステップ反復カウンタに接続されたメモリ位置読取り器と、
前記メモリ及び前記ステップ反復カウンタに接続された符号書込み器と、
が含まれる装置。
【請求項１６】
I個の符号が一組になっている誤り訂正コードの符号をインターリーブするための装置であって、
メモリと、
前記メモリに接続されたメモリイニシャライザと、
前記メモリに接続された書込みポインタセッタと、
前記書込みポインタセッタに接続されたステップ反復カウンタと、
前記メモリ及び前記ステップ反復カウンタに接続された読出しポインタセッタと、
前記メモリ及び前記ステップ反復カウンタに接続されたメモリ位置読取り器と、
前記メモリ及び前記ステップ反復カウンタに接続された符号書込み器と、
が含まれる装置。
【請求項１７】
I個の符号が一組になっている誤り訂正コードの符号をインターリーブするための装置であって、
メモリと、
前記メモリに接続されたメモリイニシャライザと、
前記メモリに接続された書込みポインタセッタと、
前記書込みポインタセッタに接続されたステップ反復カウンタと、
前記メモリ及び前記ステップ反復カウンタに接続されたメモリ位置読取り器と、
前記メモリ及び前記ステップ反復カウンタに接続された符号書込み器と、
が含まれる装置。
【請求項１８】
I個の符号が一組になっている誤り訂正コードの符号をインターリーブするための装置であって、
Jを遅延値とすると、サイズI(I-1)*J/2+1のメモリ中の初期位置にプレースホルダを設定するための手段と、
I個の受信符号毎に、
0のステップからI-1のステップまで反復的に計数するための手段であって、次の段階、即ち、
a)書込みポインタを前記プレースホルダに等しく設定する段階と、
b)ステップが0である場合、前記プレースホルダを読出しポインタに等しく設定する段階と、
c)ステップが0でない場合、前記プレースホルダをステップ*Jメモリ位置進ませる段階であって、前記プレースホルダ値が前記メモリの末尾を過ぎた場合、折り返す前記段階と、
d)前記読出しポインタを前記プレースホルダに等しく設定する段階と、
e)前記読出しポインタによって示される前記メモリ中の位置から読出す段階と、
f)前記書込みポインタによって示される前記メモリ中の位置に前記I個の符号における次の符号を書込む段階であって、ステップが0でなければ、この場合、バイパスされる前記段階と、を実施する前記手段と、
が含まれる装置。
【請求項１９】
請求項18に記載の装置であって、
前記プレースホルダを進ませる前記段階には、前記メモリサイズを法として、ステップ*Jを前記プレースホルダに加算する段階が含まれる装置。
【請求項２０】
請求項18に記載の装置であって、
前記プレースホルダを進ませる前記段階には、前記メモリサイズを法として、ステップ*Jを前記プレースホルダから減算する段階が含まれる装置。
【請求項２１】
請求項18に記載の装置であって、
符号が、それを遅延無しで送信することによってバイパスされる装置。
【請求項２２】
I個の符号が一組になっている誤り訂正コードの符号をインターリーブするための装置であって、
Jを遅延値とすると、サイズI(I-1)*J/2+I+1のメモリ中の初期位置に書込みポインタを設定するための手段と、
I個の受信符号毎に、
0のステップからI-1のステップまで反復的に計数するための手段であって、次の段階、即ち、
a)読出しポインタを前記書込みポインタの１メモリ位置後ろに等しく設定する段階であって、前記読出しポインタが前記メモリの末尾を過ぎた場合、折り返す前記段階と、
b)前記読出しポインタによって示される前記メモリ中の位置から読出す段階と、
c)前記書込みポインタによって示される前記メモリ中の位置に前記I個の符号における次の符号を書込む段階と、
d)前記書込みポインタを(ステップ+1)*Jメモリ位置進ませる段階であって、前記書込みポインタが前記メモリの末尾を過ぎた場合、折り返す前記段階と、を実施する前記手段と、
が含まれる装置。
【請求項２３】
請求項22に記載の装置であって、
前記書込みポインタを進ませる前記段階には、前記メモリサイズを法として、ステップ*Jを前記書込みポインタに加算する段階が含まれる装置。
【請求項２４】
請求項22に記載の装置であって、
前記書込みポインタを進ませる前記段階には、前記メモリサイズを法として、ステップ*Jを前記書込みポインタから減算する段階が含まれる装置。
【請求項２５】
請求項22に記載の装置であって、
１メモリ位置後ろは、１メモリ位置小さいに等しい装置。
【請求項２６】
請求項22に記載の装置であって、
１メモリ位置後ろは、１メモリ位置大きいに等しい装置。
【請求項２７】
I個の符号が一組になっている誤り訂正コードの符号をインターリーブするための装置であって、
Jを遅延値とすると、サイズI(I-1)*J/2+I+1のメモリ中の初期位置に書込みポインタを設定するための手段と、
I個の受信符号毎に、
0のステップからI-1のステップまで反復的に計数するための手段であって、次の段階、即ち、
a)前記書込みポインタの１メモリ位置後ろにある前記メモリ中の位置から読出す段階であって、前記位置が前記メモリの末尾を過ぎた場合、折り返す前記段階と、
c)前記書込みポインタによって示される前記メモリ中の位置に前記I個の符号における次の符号を書込む段階と、
d)前記書込みポインタを(ステップ+1)*Jメモリ位置進ませる段階であって、前記書込みポインタが前記メモリの末尾を過ぎた場合、折り返す前記段階と、を実施する前記手段と、
が含まれる装置。
【請求項２８】
請求項27に記載の装置であって、
前記書込みポインタを進ませる前記段階には、前記メモリサイズを法として、ステップ*Jを前記書込みポインタに加算する段階が含まれる装置。
【請求項２９】
請求項27に記載の装置であって、
前記書込みポインタを進ませる前記段階には、前記メモリサイズを法として、ステップ*Jを前記書込みポインタから減算する段階が含まれる装置。
【請求項３０】
請求項27に記載の装置であって、
１メモリ位置後ろは、１メモリ位置小さいに等しい装置。
【請求項３１】
請求項27に記載の装置であって、
１メモリ位置後ろは、１メモリ位置大きいに等しい装置。
【請求項３２】
機械によって読取可能なプログラム記憶装置であり、I個の符号が一組になっている誤り訂正コードの符号をインターリーブするための方法を実施するためにその機械によって実行可能な命令のプログラムを実際に組み入れる前記プログラム記憶装置であって、前記方法には、
Jを遅延値とすると、サイズI(I-1)*J/2+1のメモリ中の初期位置にプレースホルダを設定する段階、が含まれ、
I個の受信符号毎に、
0のステップからI-1のステップまで反復的に計数し、次の段階、即ち、
a)書込みポインタを前記プレースホルダに等しく設定する段階と、
b)ステップが0である場合、前記プレースホルダを読出しポインタに等しく設定する段階と、
c)ステップが0でない場合、前記プレースホルダをステップ*Jメモリ位置進ませる段階であって、前記プレースホルダ値が前記メモリの末尾を過ぎた場合、折り返す前記段階と、
d)前記読出しポインタを前記プレースホルダに等しく設定する段階と、
e)前記読出しポインタによって示される前記メモリ中の位置から読出す段階と、
f)前記書込みポインタによって示される前記メモリ中の位置に前記I個の符号における次の符号を書込む段階であって、ステップが0でなければ、この場合、バイパスされる前記段階と、を実施する前記方法であるプログラム記憶装置。
【請求項３３】
機械によって読取可能なプログラム記憶装置であり、I個の符号が一組になっている誤り訂正コードの符号をインターリーブするための方法を実施するためにその機械によって実行可能な命令のプログラムを実際に組み入れる前記プログラム記憶装置であって、前記方法には、
Jを遅延値とすると、サイズI(I-1)*J/2+I+1のメモリ中の初期位置に書込みポインタを設定する段階、が含まれ、
I個の受信符号毎に、
0のステップからI-1のステップまで反復的に計数し、次の段階、即ち、
a)読出しポインタを前記書込みポインタの１メモリ位置後ろに等しく設定する段階であって、前記読出しポインタが前記メモリの末尾を過ぎた場合、折り返す前記段階と、
b)前記読出しポインタによって示される前記メモリ中の位置から読出す段階と、
c)前記書込みポインタによって示される前記メモリ中の位置に前記I個の符号における次の符号を書込む段階と、
d)前記書込みポインタを(ステップ+1)*Jメモリ位置進ませる段階であって、前記書込みポインタが前記メモリの末尾を過ぎた場合、折り返す前記段階と、を実施する前記方法であるプログラム記憶装置。
【請求項３４】
機械によって読取可能なプログラム記憶装置であり、I個の符号が一組になっている誤り訂正コードの符号をインターリーブするための方法を実施するためにその機械によって実行可能な命令のプログラムを実際に組み入れる前記プログラム記憶装置であって、前記方法には、
Jを遅延値とすると、サイズI(I-1)*J/2+I+1のメモリ中の初期位置に書込みポインタを設定する段階、が含まれ、
I個の受信符号毎に、
0のステップからI-1のステップまで反復的に計数し、次の段階、即ち、
a)前記書込みポインタの１メモリ位置後ろにある前記メモリ中の位置から読出す段階であって、前記位置が前記メモリの末尾を過ぎた場合、折り返す前記段階と、
c)前記書込みポインタによって示される前記メモリ中の位置に前記I個の符号における次の符号を書込む段階と、
d)前記書込みポインタを(ステップ+1)*Jメモリ位置進ませる段階であって、前記書込みポインタが前記メモリの末尾を過ぎた場合、折り返す前記段階と、
を実施する前記方法であるプログラム記憶装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信システムに関し、特に、誤り訂正コードをインターリーブするための解決策に関する。
【背景技術】
【０００２】
デジタルデータが、潜在的に雑音チャネルになる可能性があるチャネルを介して送信される場合、少なくとも限定した数の誤りに対する復旧手段を持つことは重要である。これらの誤りは、雑音又は他の環境因子によってデータストリームに導入されることがある。誤りを有するデータを復旧するプロセスは、誤り訂正として知られている。誤り訂正は、一般的に、ある数の冗長データ片を通信対象のデータ列に加えることによって実現される。受信機は、送信された元のメッセージの再構築を試みる場合、初めに、符号化メッセージの破壊された可能性があるものを調査し、そして、(もしあれば)どのデータを訂正すべきかについて判断し得る。
【０００３】
全ての可能な符号化メッセージの組は、誤り訂正コードとして知られている。一般的には、２つのタイプの誤り訂正コード、即ち、ブロックタイプのコード及び畳込みタイプのコードが存在する。ブロックタイプのコードは、n>kとすると、情報列をk個のデータ片ブロックに分割して、長さnのコードワードを生成する。エンコーダがブロックタイプのコードを用いている場合、システムは、情報列のk個のデータ片を選択し、全てのk個のデータ片をバッファに配置する。そして、関数が、k個のブロック全体に適用され、コードワードを生成する。しかしながら、メッセージが、大きなブロックでよりもむしろ直列に入ってくるアプリケーションも幾つか存在し、この場合、バッファを用いると好ましくないことがある。これらの場合、畳込みタイプのコードを利用し得る。畳込みコーダは、2を法とする畳込みに基づき、冗長データ片を生成する。畳込みコーダは、過去のデータ片並びに現在のデータ片を利用して、コードワードを生成することから、有限状態機械であると見なし得る。
【０００４】
ブロックタイプコード及び畳込みコードを共に用いて、性能及び効率を改善し得る。例えば、ブロックタイプコードを用いて、情報をコード化し、その情報を表す一連の符号を生成し得る。そして、畳込みコードを用いて、符号をコード化し得る。これによって、追加の保護層が提供されるが、バースト及びランダム誤りの取扱いも改善し得る。このようなシステム用の通常の設計には、リードソロモンブロックコードを含み、畳込みコード化を伴い得る。リードソロモンコードは、巡回コードとして知られている特殊なタイプのブロックコードである。巡回コードは、コードにおける任意の２つのコードワードの和もまたコードワードであるコードであり、また、コードにおけるコードワードの任意の周期的シフトもまたコードワードである。体GF(2ν)における基本要素をαとすると、即ち、α2ν-1=1とすると、i≠0の場合、2ν-1を法として、αi≠1である。長さｎ=2ν-1のリードソロモン(RS)コード及び次元kは、g(x)=(x-a)(x-a2)・・・(x-an-k-1)(x-an-k)によって生成される巡回コードである。
【０００５】
畳込みコードを用いることによるバースト及びランダム誤りの取扱いは、RS符号を時間的にインターリーブすることによって更に改善し得る。これによって、あらゆる潜在的な誤りが多数のRSコードワード間に分散され、こうして、一度に発生するが単純なRS復号処理が取り扱い得るよりも恐らく長く続く干渉による復旧の変動が改善される。従って、バーストにより結果的に生じるRSコードワード当たりの誤りは、RSコードの訂正能力内にあると思われる。
【０００６】
畳込みインターリーバは、通常、組内の各符号の遅延を大きくすることによって、符号を分散する。任意の２つの符号間における遅延の増加は、Jによって示され、また、組における符号の数は、Iによって示し得る。
【０００７】
インターリーブ機能を記述する１つの方法は、I数の行のFIFOメモリ(FIFO)であって、各FIFOが先行のものよりJ個の要素だけ深いFIFOを示すことである。図1は、代表的なインターリーバ及びデインターリーバを示す図である。第１位置100は、遅延が必要とされないため、いずれのFIFOも有する必要はない。次の位置102は、長さJのFIFOを有する。次の位置104は、長さ2*JのFIFOを有し、以降、I番目の位置106が長さI*JのFIFOを有するまで同様である。交換子は、符号が送信される毎に次の位置に進み、I番目の位置に到達した後、折り返して1番目の位置に戻る。従って、データは、最初に受信されると、第１行に設定し得る。新しいRS符号が行に書き込まれるにつれて、その行の最も古い値が読み出され、行ポインタは、１つだけ進む。最終行(I)が終わると、ポインタは、第１行にリセットされ、このシーケンスを繰り返す。これによって、符号がインターリーブされる。同様なプロセスが、デインターリーバで起こり、元の符号シーケンスに到達し得る。
【０００８】
この設計の単純明快な実施例には、メモリにおける幾つかの静的なFIFOメモリ(FIFO)を含み得る。新しいデータは、FIFOに書き込まれると、最も古いデータと置き換わる。この実施例の欠点は、FIFO用の読出し及び書込みポインタを維持するための大量の記憶容量が必要なことである。各FIFOには、それ自体の読出し及び書込みポインタが必要であり、従って、I個の読出し及び書込みポインタを必要とする。
【０００９】
この問題に対するもう１つの可能な解決策は、ポインタよりもむしろ、ルックアップテーブルを用いて、このシーケンスにおける特定のポイントでの読出し又は書込みに必要なアドレスを計算するように実施例を変形することである。これによって、総ポインタ記憶容量並びにアドレス計算ロジックが低減される。残念ながら、代表的な実施例用のアクセスパターンは、ほぼ264ビットの計数の間、繰り返しがない。従って、これによって、ルックアップテーブルのサイズが異常になり、この実施例は実現不可能になる。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
必要なことは、メモリポインタ計算を実用的に維持しつつインターリーバメモリを最小限にする解決策である。
【課題を解決するための手段】
【００１１】
メモリは、仕切ることによって絶えずスライドするFIFOに分割し得る。各FIFOは、メモリ中に縦列に積層して、最も古いデータをベースオフセットに、また、最新データを末尾に（又は反対に）配置し得る。各符号、ポインタは、適切な量(通常、先行の符号の場合よりJ以上)だけ(組サイズを法として)インクリメントし得る。各組の後、ポインタを先行のインクリメントよりJ以上だけインクリメントして、プロセスが始まり、メモリの末尾に到達すると、メモリを折り返し得る。予め設定された数の符号に達した後、プロセスは、インクリメントJから再開し得る。他の選択肢として、ポインタは、インクリメントよりもむしろデクリメントし得る。従って、最新符号は、現在のFIFOにおける最も古い符号が明け渡したメモリ位置を割り込んで利用し、FIFOをスライドさせ、誤り訂正コードインターリーブ処理のために、極めて効率的で信頼性のあるメモリの使用方法を提供する。
【発明を実施するための最良の形態】
【００１２】
この明細書に組み込まれその一部を構成する添付図面は、本発明の１つ又は複数の実施形態を示し、また、詳細な説明と共に本発明の原理及び実施例を説明する役割を果たす。
【００１３】
本発明の実施形態について、本明細書において、コンピュータシステムの遠隔性能分析及び最適化ためのシステム及び方法の文脈で述べる。当業者は、以下の本発明の詳細な説明が、例示のみであり、決して制限することを意図するものではないことを認識されたい。本発明の他の実施形態は、そのような本開示の恩恵を有する当業者者が容易に思い浮かべるものである。添付図面に示す本発明の実施例について、これから詳細に説明する。同じ参照符号を図面及び以下の詳細な説明全体に用いて、同じ又は同様な部品を参照する。
【００１４】
分かり易くするために、本明細書で記述する実施例の慣例的な特徴については、全てを示さずまた説明しない。勿論、このようなあらゆる実際の実施例の開発では、用途及び業務に関連する制約事項への遵守等、開発者の特定の目標を達成するために、数多くの実施例特有の判断を行わねばならないこと、また、これらの特定の目標は、実施例毎にまた開発者毎に変わることを理解されたい。更に、このような開発の努力は、複雑でまた手間のかかるものであるが、それにも関わらず本開示の恩恵を有する当業者にとっては、日常的な技術への取り組みであることを理解されたい。
【００１５】
本発明に基づき、構成要素、プロセスステップ、及び/又はデータ構造は、様々なタイプのオペレーティングシステム、コンピュータ処理プラットフォーム、コンピュータプログラム、及び/又は汎用機械を用いて、実現し得る。
【００１６】
本発明は、メモリを仕切って絶えずスライドするFIFOに分割する解決策を提供する。各FIFOの記憶領域は、メモリ中に縦列に積層され、最も古いデータがベースオフセットに、また、最新データが末尾に配置される。本発明の一実施形態では、１つの読出しポインタ及び１つの書込みポインタだけが必要である。もう１つの実施形態においては、１つの書込みポインタを既知の数式に用いて、読出しポインタを計算し得る。各符号、ポインタは、適切な量(通常、先行の符号の場合よりJ以上)だけ(組サイズを法として)インクリメントし得る。各組の後、ポインタを先行のインクリメントよりJ以上だけインクリメントして、プロセスが始まり、メモリの末尾に到達すると、メモリを折り返し得る。予め設定された数の符号に達した後、プロセスは、インクリメントJから再開し得る。
【００１７】
留意されたいことは、本明細書において、ポインタが符号毎にインクリメントされる実施例について述べる一方で、本発明は、ポインタが符号毎にデクリメントされる実施形態に用い得ることを当業者は認識されたい。
【００１８】
本発明には、異なる目標を達成するために利用し得る幾つかの変形例が存在する。開発者が、インターリーバに必要な処理ロジックを最適化したい場合、第１符号に対して遅延を有さない(また、対応するFIFOがない)よりもむしろ、FIFOを加えることによって遅延が導入される実施例を選択し得る。これによって、後で分かるように、読出し及び書込みポインタの計算が簡素化される。しかしながら、これによって、I個の各FIFOがほぼブロックだけ増加するにつれて、I個の項目が追加され、また、一定の１符号遅延が全システム待ち時間に追加される。従って、開発者は、メモリを最適化したい場合、第１符号が遅延を有さない実施例を選択し得る。更に、開発者は、読出し及び書込みポインタ双方を記憶する実施例と、書込みポインタだけを含み、読出しポインタは既知の数式を用いて計算される実施例との間で選択し得る。書込みポインタだけを有すると、必要な記憶容量が低減されるが、数式を用いて読出しポインタを計算する必要があるため、ロジックが追加される。
【００１９】
図２は、本発明の実施形態に基づく、FIFOをスライドすることによる読出し及び書込みポインタの進行を示す図である。本実施形態において、読出し及び書込みポインタ双方が、ロジックの量を低減するために維持される。更に、遅延は、第１符号に対して導入されず、従って、FIFOは、第１符号に対して必要ではない。本実施形態において、I(I-1)*J/2+1のメモリ位置が必要である。第１符号は、FIFOを必要としないが、第２符号には、長さJのFIFOが必要であり、第３には、長さ2JのFIFO等々が必要である。後で分かるように、周辺の他の15タイルをスライドするために１つの位置が空でなければならない"マジック15"パズルゲームと同様に、末尾における追加の位置は、スライド処理の側面を達成するために必要である。
【００２０】
符号が処理される各時間は、サイクルとしても知られている。或るポイントにおいて、符号は、サイクルが、"向きを変えて"即ち0に戻って、開始するポイントに到達する。
【００２１】
読出し及び書込みの進行は、次のプロセスに従って続行し得るが、ここでは、wrは、書込みポインタであり、rdは、読出しポインタであり、wr_newは、プレースホルダ変数であり、ステップは、ステップ値を示す。即ち、
1)（FIFOはスライドすることから、初期位置は妥当ではないため）wrを任意の値に初期化する。
2)rdをwrに初期化する。
次に、0からI-1までの各ステップにおいて、次のように、3、4、5、6、及び7を繰り返す。
3) wr=wr_newと設定。
4) wr_new=(ステップ+wr_new)・モジュロ・メモリのサイズと設定、ステップ=0でなければ、この場合、wr_new=rdと設定。
5)rd=wr_newと設定。
6)rdにおいて値を読み出す。
7)wrにおいて新しい値を書き込む。
【００２２】
ステップは、I-1に達すると、単純に0に戻り、ステップ3-7は、新しい符号が受信されなくなる時まで繰り返し得る。このプロセスは、繰り返し毎にステップの加算よりもむしろその減算に容易に変形でき、FIFOを他の方向にスライドし得ることに留意されたい。FIFOがスライドする方向は、重要な方向にFIFOがスライドするという事実には関係しない。
【００２３】
従って、図2に戻ると、Iを5とし、Jを1バイトと仮定し得る。従って、実質的に、長さ1で始まり、長さが増加する4つのFIFOが存在するが、実際は、単に、サイズ11バイトのメモリが存在し、FIFOが、このメモリを中心にしてスライドする。図2は、メモリ位置が0乃至10であるこのFIFOを示す。読出しポインタは、表1に従って、進行し得る。
【表１】
2006521059.tif 000002
【００２４】
書込みポインタは、表2に従って進行し得る。
【表２】
2006521059.tif 000003
【００２５】
従って、第１符号は、バイパスであるサイクル0にあり、従って、FIFOに配置されない。第２符号は、サイクル1にあり、読出しが(現時点で空である)位置1から起こり、符号は、位置0に書き込まれる。第３符号は、サイクル2にあり、読出しが位置3(空)から起こり、符号は、位置1に書き込まれる。第４符号は、サイクル3にあり、読出しが位置6(空)から起こり、符号は、位置3に書き込まれる。第５符号は、サイクル4にあり、読出しが位置10(空)から起こり、符号は、位置6に書き込まれる。第６符号は、0においてサイクルを再開し、従って、バイパスである。第７符号は、サイクル1にあり、読出しが、(サイクル1において書き込まれた値を有する)位置0から起こり、符号は、位置10に書き込まれる。従って、"第１FIFO"に対する適切な遅延1が実現された。このプロセスは、残された符号がなくなるまでいつまでも続く。
【００２６】
図3は、本発明のもう１つの実施形態に基づく、FIFOをスライドすることによる読出し及び書込みポインタの進行を示す図である。本実施形態において、追加の遅延(従って、追加のメモリ位置)が各FIFOに対して導入され、バイパスは用いられない。これによって、I(I-1)*J/2+I+1個のメモリ位置が必要になる。従って、Iが再度5であり、Jが1であるならば、16個のメモリ位置が必要である。
【００２７】
従って、図3に戻ると、メモリ位置0乃至15を提供し得る。読出し及び書込みの進行は、次のプロセスに従って続行し得るが、この場合、wrは書込みポインタであり、rdは読出しポインタであり、ステップは、ステップ値を示す。
1)（FIFOはスライドすることから、初期位置は妥当ではないため）wrを任意の値に初期化する。
次に、0からI-1までの各ステップにおいて、次のように、2、3、4、5、6、及び7を繰り返す。
2) rd=wr-1と設定。
3)rdにおいて値を読み出す。
4)wrにおいて新しい値を書き込む。
5)wr=wr+(ステップ+1)*Jと設定。
【００２８】
読出しポインタは、表3に従って進行し得る。
【表３】
2006521059.tif 000004
【００２９】
書込みポインタは、表4に従って進行し得る。
【表４】
2006521059.tif 000005
【００３０】
図4は、本発明の実施形態に基づく、I個の符号が一組になっている誤り訂正コードの符号をインターリーブするための方法を示すフロー図である。本実施形態は、図2に示し対応する文で説明した実施形態と同様である。400において、プレースホルダは、Jを遅延値(即ち、各メモリ位置のサイズ)とすると、サイズI(I-1)*J/2+1のメモリ中の初期位置に設定し得る。そして、符号の受信が始まる。I個の受信符号毎に、次のループが実行される。このループにおいて、ステップは、0からI-1までカウントされ、各繰り返しにおいて、一連のアクションを実施し得る。従って、0からI-1までのステップを全てカウントすることによって、また、I個の各符号に対してその計数を繰り返すことによって、プロセスは、反復的に計数していると言われる。
【００３１】
402において、書込みポインタは、プレースホルダに等しく設定し得る。404において、ステップが0である場合、プレースホルダは、読出しポインタに等しく設定し得る。406において、ステップが0ではない場合、プレースホルダは、ステップ*Jメモリ位置進み、プレースホルダ値がメモリの末尾を過ぎた場合、折り返し得る。プレースホルダを進める段階には、どの方向にFIFOがスライドするかに応じて、ステップ*Jをプレースホルダに加算する段階又はステップ*Jをプレースホルダから減算する段階のいずれかが含まれる。折り返しは、この和又は差を取り、モジュロ・メモリサイズをそれに適用することによって、発生し得る。408において、読出しポインタは、プレースホルダに等しく設定し得る。410において、符号は、読出しポインタによって示されるメモリ中の位置から読み出し得る。412において、I個の符号における次の符号は、書込みポインタによって示されるメモリ中の位置に書き込み得るが、ステップが0でなければ、この場合、414において、バイパスされる。符号は、それを遅延無しで送信することによってバイパスし得る。
【００３２】
図5は、本発明のもう１つの実施形態に基づく、I個の符号が一組になっている誤り訂正コードの符号をインターリーブするための方法を示すフロー図である。本実施形態は、図3に示し対応する文で説明した実施形態と同様である。本実施形態では、読出し及び書込みポインタの双方が記憶される。500において、Jを遅延値(即ち、各メモリ位置のサイズ)とすると、書込みポインタは、サイズI(I-1)*J/2+I+1のメモリ中の初期位置に設定し得る。そして、符号の受信が始まる。I個の受信符号毎に、次のループが実行される。このループにおいて、ステップは、0からI-1までカウントされ、各繰り返しにおいて、一連のアクションを実施し得る。従って、0からI-1までのステップを全てカウントすることによって、また、I個の各符号に対してその計数を繰り返すことによって、プロセスは、反復的に計数していると言われる。
【００３３】
502において、読出しポインタは、書込みポインタの１メモリ位置後ろに等しく設定され、読出しポインタがメモリの末尾を過ぎた場合、折り返し得る。１メモリ位置後ろは、FIFOがスライドする方向に応じて、１メモリ位置小さい又は１メモリ位置大きいのいずれかと等しい可能性がある。折り返しは、この和又は差を取り、モジュロ・メモリサイズをそれに適用することによって、発生し得る。504において、符号は、読出しポインタによって示されるメモリ中の位置から読み出し得る。506において、I個の符号における次の符号は、書込みポインタによって示されるメモリ中の位置に書き込み得る。508において、書込みポインタは、(ステップ+l)*Jメモリ位置進み、書込みポインタがメモリの末尾を過ぎた場合、折り返し得る。書込みポインタを進める段階には、どの方向にFIFOがスライドするかに応じて、(ステップ+l)*Jを書込みポインタに加算する段階又は(ステップ+l)*Jを書込みポインタから減算する段階のいずれかを含み得る。折り返しは、この和又は差を取り、モジュロ・メモリサイズをそれに適用することによって、発生し得る。
【００３４】
図6は、本発明の第３の実施形態に基づく、I個の符号が一組になっている誤り訂正コードの符号をインターリーブするための方法を示すフロー図である。本実施形態は、図5に示し対応する文で説明した実施形態と同様であるが、例外は、本実施形態において、書込みポインタだけが記憶されることである。600において、書込みポインタは、Jを遅延値(即ち、各メモリ位置のサイズ)とすると、サイズI(I-1)*J/2+I+1のメモリ中の初期位置に設定し得る。そして、符号の受信が始まる。I個の受信符号毎に、次のループが実行される。このループにおいて、ステップは、0からI-1までカウントされ、各繰り返しにおいて、一連のアクションを実施し得る。従って、0からI-1までのステップを全てカウントすることによって、また、I個の各符号に対してその計数を繰り返すことによって、プロセスは、反復的に計数していると言われる。
【００３５】
602において、符号は、書込みポインタの１メモリ位置後ろに等しいメモリ中の位置から読出され、この位置がメモリの末尾を過ぎた場合、折り返し得る。１メモリ位置後ろは、FIFOがスライドする方向に応じて、１メモリ位置小さい又は１メモリ位置大きいのいずれかと等しい可能性がある。折り返しは、この和又は差を取り、モジュロ・メモリサイズをそれに適用することによって、発生し得る。604において、I個の符号における次の符号は、書込みポインタによって示されるメモリ中の位置に書き込み得る。606において、書込みポインタは、(ステップ+l)*Jメモリ位置進み、書込みポインタがメモリの末尾を過ぎた場合、折り返し得る。書込みポインタを進める段階には、どの方向にFIFOがスライドするかに応じて、(ステップ+l)*Jを書込みポインタに加算する段階又は(ステップ+l)*Jを書込みポインタから減算する段階のいずれかを含み得る。折り返しは、この和又は差を取り、モジュロ・メモリサイズをそれに適用することによって、発生し得る。
【００３６】
図7は、本発明の実施形態に基づく、I個の符号が一組になっている誤り訂正コードの符号をインターリーブするための装置を示すブロック図である。提供されるメモリ700は、FIFO及び計算に用いられる任意の変数を記憶し得る。メモリ700に接続されたメモリイニシャライザ702は、JをFIFO用の遅延値(即ち、各メモリ位置のサイズ)とすると、メモリ中のサイズI(I-1)*J/2+1のメモリに領域を設定し得る。メモリ700に接続されたプレースホルダセッタ704は、プレースホルダをメモリ中の初期位置に設定し得る。そして、符号の受信が始まる。I個の受信符号毎に、ループが実行される。このループにおいて、ステップは、0からI-1までカウントされ、各繰り返しにおいて、一連のアクションを実施し得る。従って、0からI-1までのステップを全てカウントすることによって、また、I個の各符号に対してその計数を繰り返すことによって、プロセスは、反復的に計数していると言われる。プレースホルダセッタ704に接続されたステップ反復カウンタ706は、この反復計数を行い、また、ループを制御し得る。これ以降、メモリと称されるものは、実際、FIFO用に確保されたメモリ部分である。
【００３７】
メモリ700及びステップ反復カウンタ706に接続された書込みポインタセッタ708は、書込みポインタをプレースホルダに等しく設定し得る。ステップが0である場合、プレースホルダセッタ704は、プレースホルダを読出しポインタに等しく設定し得る。ステップが0ではない場合、プレースホルダセッタ704は、プレースホルダをステップ*Jメモリ位置進ませ、プレースホルダ値がメモリの末尾を過ぎた場合、折り返し得る。プレースホルダを進める段階には、どの方向にFIFOがスライドするかに応じて、ステップ*Jをプレースホルダに加算する段階又はステップ*Jをプレースホルダから減算する段階のいずれかが含まれる。折り返しは、この和又は差を取り、モジュロ・メモリサイズをそれに適用することによって、発生し得る。メモリ700及びステップ反復カウンタ706に接続された読出しポインタセッタ710は、読出しポインタをプレースホルダに等しく設定し得る。そして、メモリ700及びステップ反復カウンタ706に接続されたメモリ位置読取り器712は、読出しポインタによって示されるメモリ中の位置から符号を読み出し得る。そして、メモリ700及びステップ反復カウンタ706に接続された符号書込み器714は、I個の符号における次の符号を書込みポインタによって示されるメモリ中の位置に書き込み得るが、ステップが0でなければ、この場合、バイパスされる。符号は、それを遅延無しで送信することによって、バイパスし得る。
【００３８】
図8は、本発明のもう１つの実施形態に基づく、I個の符号が一組になっている誤り訂正コードの符号をインターリーブするための装置を示すブロック図である。提供されるメモリ800は、FIFO及び計算に用いられる任意の変数を記憶し得る。メモリ800に接続されたメモリイニシャライザ802は、JをFIFO用の遅延値(即ち、各メモリ位置のサイズ)とすると、サイズI(I-1)*J/2+I+1のメモリに領域を設定し得る。メモリ800に接続された書込みポインタセッタ804は、書込みポインタをメモリ中の初期位置に設定し得る。そして、符号の受信が始まる。I個の受信符号毎に、ループが実行される。このループにおいて、ステップは、0からI-1までカウントされ、各繰り返しにおいて、一連のアクションを実施し得る。従って、0からI-1までのステップを全てカウントすることによって、また、I個の各符号に対してその計数を繰り返すことによって、プロセスは、反復的に計数していると言われる。書込みポインタセッタ804に接続されたステップ反復カウンタ806は、この反復計数を行い、また、ループを制御し得る。これ以降、メモリと称されるものは、実際、FIFO用に確保されたメモリ部分である。
【００３９】
メモリ800及びステップ反復カウンタ806に接続された読出しポインタセッタ808は、読出しポインタを書込みポインタの１メモリ位置後ろに等しく設定し、読出しポインタがメモリの末尾を過ぎた場合、折り返し得る。１メモリ位置後ろは、FIFOがスライドする方向に応じて、１メモリ位置小さい又は１メモリ位置大きいのいずれかと等しい可能性がある。折り返しは、この和又は差を取り、モジュロ・メモリサイズをそれに適用することによって、発生し得る。メモリ800及びステップ反復カウンタ806に接続されたメモリ位置読取り器810は、読出しポインタによって示されるメモリ中の位置から符号を読み出し得る。メモリ800及びステップ反復カウンタ806に接続された符号書込み器812は、I個の符号における次の符号を書込みポインタによって示されるメモリ中の位置に書き込み得る。そして、書込みポインタセッタ808は、(ステップ+l)*Jメモリ位置進み、書込みポインタがメモリの末尾を過ぎた場合、折り返し得る。書込みポインタを進める段階には、どの方向にFIFOがスライドするかに応じて、(ステップ+l)*Jを書込みポインタに加算する段階又は(ステップ+l)*Jを書込みポインタから減算する段階のいずれかを含み得る。折り返しは、この和又は差を取り、モジュロ・メモリサイズをそれに適用することによって、発生し得る。
【００４０】
図8は、本発明のもう１つの実施形態に基づく、I個の符号が一組になっている誤り訂正コードの符号をインターリーブするための装置を示すブロック図である。提供されるメモリ800は、FIFO及び計算に用いられる任意の変数を記憶し得る。メモリ800に接続されたメモリイニシャライザ802は、JをFIFO用の遅延値(即ち、各メモリ位置のサイズ)とすると、サイズI(I-1)*J/2+I+1のメモリに領域を設定し得る。メモリ800に接続された書込みポインタセッタ804は、書込みポインタをメモリ中の初期位置に設定し得る。そして、符号の受信が始まる。I個の受信符号毎に、ループが実行される。このループにおいて、ステップは、0からI-1までカウントされ、各繰り返しにおいて、一連のアクションを実施し得る。従って、0からI-1までのステップを全てカウントすることによって、また、I個の各符号に対してその計数を繰り返すことによって、プロセスは、反復的に計数していると言われる。書込みポインタセッタ804に接続されたステップ反復カウンタ806は、この反復計数を行い、また、ループを制御し得る。これ以降、メモリと称されるものは、実際、FIFO用に確保されたメモリ部分である。
【００４１】
メモリ800及びステップ反復カウンタ806に接続された読出しポインタセッタ808は、読出しポインタを書込みポインタの１メモリ位置後ろに等しく設定し、読出しポインタがメモリの末尾を過ぎた場合、折り返し得る。１メモリ位置後ろは、FIFOがスライドする方向に応じて、１メモリ位置小さい又は１メモリ位置大きいのいずれかと等しい可能性がある。折り返しは、この和又は差を取り、モジュロ・メモリサイズをそれに適用することによって、発生し得る。メモリ800及びステップ反復カウンタ806に接続されたメモリ位置読取り器810は、読出しポインタによって示されるメモリ中の位置から符号を読み出し得る。メモリ800及びステップ反復カウンタ806に接続された符号書込み器812は、I個の符号における次の符号を書込みポインタによって示されるメモリ中の位置に書き込み得る。そして、書込みポインタセッタ808は、(ステップ+l)*Jメモリ位置進み、書込みポインタがメモリの末尾を過ぎた場合、折り返し得る。書込みポインタを進める段階には、どの方向にFIFOがスライドするかに応じて、(ステップ+l)*Jを書込みポインタに加算する段階又は(ステップ+l)*Jを書込みポインタから減算する段階のいずれかを含み得る。折り返しは、この和又は差を取り、モジュロ・メモリサイズをそれに適用することによって、発生し得る。
【００４２】
図9は、本発明の第３の実施形態に基づく、I個の符号が一組になっている誤り訂正コードの符号をインターリーブするための装置を示すブロック図である。メモリ900は、FIFO及び計算に用いられる任意の変数を記憶し得る。メモリ900に接続されたメモリイニシャライザ902は、JをFIFO用の遅延値(即ち、各メモリ位置のサイズ)とすると、サイズI(I-1)*J/2+I+1のメモリに領域を設定し得る。メモリ900に接続された書込みポインタセッタ904は、書込みポインタをメモリ中の初期位置に設定し得る。そして、符号の受信が始まる。I個の受信符号毎に、ループが実行される。このループにおいて、ステップは、0からI-1までカウントされ、各繰り返しにおいて、一連のアクションを実施し得る。従って、0からI-1までのステップを全てカウントすることによって、また、I個の各符号に対してその計数を繰り返すことによって、プロセスは、反復的に計数していると言われる。書込みポインタセッタ804に接続されたステップ反復カウンタ906は、この反復計数を行い、また、ループを制御し得る。これ以降、メモリと称されるものは、実際、FIFO用に確保されたメモリ部分である。
【００４３】
メモリ900及びステップ反復カウンタ906に接続されたメモリ位置読取り器908は、書込みポインタの１メモリ位置後ろにあるメモリ位置に等しいメモリ中の位置から読出され、この位置がメモリの末尾を過ぎた場合、折り返し得る。１メモリ位置後ろは、FIFOがスライドする方向に応じて、１メモリ位置小さい又は１メモリ位置大きいのいずれかと等しい可能性がある。折り返しは、この和又は差を取り、モジュロ・メモリサイズをそれに適用することによって、発生し得る。メモリ900及びステップ反復カウンタ906に接続された符号書込み器910は、書込みポインタによって示されるメモリ中の位置に書き込み得る。書込みポインタセッタ908は、書込みポインタを(ステップ+l)*Jメモリ位置進ませ、書込みポインタがメモリの末尾を過ぎた場合、折り返し得る。書込みポインタを進める段階には、どの方向にFIFOがスライドするかに応じて、(ステップ+l)*Jを書込みポインタに加算する段階又は(ステップ+l)*Jを書込みポインタから減算する段階のいずれかを含み得る。折り返しは、この和又は差を取り、モジュロ・メモリサイズをそれに適用することによって、発生し得る。
【００４４】
本発明の実施形態及び応用例について示し説明したが、本開示の恩恵を有する当業者には、上述したよりも更に多くの変形例が、本明細書の新規概念から逸脱することなく可能であることが明白である。従って、本発明は、添付の請求項の精神によるもの以外制限されるものではない。
【図面の簡単な説明】
【００４５】
【図１】代表的なインターリーバ及びデインターリーバを示す図である。
【図２】本発明の実施形態に基づく、FIFOをスライドすることによる読出し及び書込みポインタの進行を示す図である。
【図３】本発明のもう１つの実施形態に基づく、FIFOをスライドすることによる読出し及び書込みポインタの進行を示す図である。
【図４】本発明の実施形態に基づく、I個の符号が一組になっている誤り訂正コードの符号をインターリーブするための方法を示すフロー図である。
【図５】本発明のもう１つの実施形態に基づく、I個の符号が一組になっている誤り訂正コードの符号をインターリーブするための方法を示すフロー図である。
【図６】本発明の第３の実施形態に基づく、I個の符号が一組になっている誤り訂正コードの符号をインターリーブするための方法を示すフロー図である。
【図７】本発明の実施形態に基づく、I個の符号が一組になっている誤り訂正コードの符号をインターリーブするための装置を示すブロック図である。
【図８】本発明のもう１つの実施形態に基づく、I個の符号が一組になっている誤り訂正コードの符号をインターリーブするための装置を示すブロック図である。
【図９】本発明の第３の実施形態に基づく、I個の符号が一組になっている誤り訂正コードの符号をインターリーブするための装置を示すブロック図である。
【符号の説明】
【００４６】
７００      メモリ
７０２      メモリイニシャライザ
７０４      プレースホルダセッタ
７０６      ステップ反復カウンタ
７０８      書込みポインタセッタ
７１０      読出しポインタセッタ
７１２      メモリ位置読取り器
７１４      符号書込み器
８００      メモリ
８０２      メモリイニシャライザ
８０４      書込みポインタセッタ
８０６      ステップ反復カウンタ
８０８      読出しポインタセッタ
８１０      メモリ位置読取り器
８１２      符号書込み器
９００      メモリ
９０２      メモリイニシャライザ
９０４      書込みポインタセッタ
９０６      ステップ反復カウンタ
９０８      メモリ位置読取り器
９１０      符号書込み器
【図１】
2006521059.tif 000006
【図２】
2006521059.tif 000007
【図３】
2006521059.tif 000008
【図４】
2006521059.tif 000009
【図５】
2006521059.tif 000010
【図６】
2006521059.tif 000011
【図７】
2006521059.tif 000012
【図８】
2006521059.tif 000013
【図９】
2006521059.tif 000014
【国際調査報告】
2006521059.tif 000015
2006521059.tif 000016