(57)【要約】【課題】メモリサイズに制約のある環境下においても、任意のブロックサイズの符号化シンボルを畳み込み符号化することが可能な装置の提供。【解決手段】入力データをブロック毎に符号化し、生成された符号化シンボルを外部記憶装置１４に蓄積する手段１２と、畳み込み符号化に必要な符号化シンボルを、外部記憶装置１４からメモリバッファ１８に転送する手段１６と、メモリバッファ１８内に配置された符号化シンボルを畳み込み符号化する手段２０とを備えた符号化装置１０。【選択図】        図１
2004320650.tif 000002
【特許請求の範囲】
【請求項１】
入力データをブロック毎に符号化し、生成された符号化シンボルを外部記憶装置に蓄積する手段と、
畳み込み符号化に必要な符号化シンボルを、上記外部記憶装置からメモリバッファに転送する手段と、
メモリバッファ内に配置された符号化シンボルを、畳み込み符号化する手段と、
を備えたことを特徴とする符号化装置。
【請求項２】
入力データをブロック毎に符号化し、生成された符号化シンボルを外部記憶装置に蓄積する手段と、
畳み込み符号化に必要な符号化シンボルを、上記外部記憶装置から最前段のメモリバッファに転送する手段と、
各メモリバッファ内に配置された符号化シンボルを、次段のメモリバッファにシフトする手段と、
最後段のメモリバッファ内に配置された符号化シンボルを、畳み込み符号化する手段と、
を備えたことを特徴とする符号化装置。
【請求項３】
入力データを畳み込み復号化し、ブロック単位の符号化シンボルを生成する手段と、
各符号化シンボルを、ブロック毎に外部記憶装置の異なるチャネルに出力する手段と、
上記外部記憶装置内の符号化シンボルを、ブロック単位で復号化する手段と、
を備えたことを特徴とする復号化装置。
【請求項４】
入力データを畳み込み復号化し、ブロック単位の符号化シンボルを生成する手段と、
各符号化シンボルを、ブロック毎にメモリバッファに出力する手段と、
ブロック毎に所定数の符号化シンボルが上記メモリバッファ内に蓄積された時点で、各符号化シンボルを外部記憶装置の一つのチャネルに出力する手段と、
上記外部記憶装置内の符号化シンボルを、ブロック単位で復号化する手段と、
を備えたことを特徴とする復号化装置。
【請求項５】
コンピュータを、
入力データをブロック毎に符号化し、生成された符号化シンボルを外部記憶装置に蓄積する手段、
畳み込み符号化に必要な符号化シンボルを、上記外部記憶装置からメモリバッファに転送する手段、
メモリバッファ内に配置された符号化シンボルを、畳み込み符号化する手段、
として機能させることを特徴とする符号化プログラム。
【請求項６】
コンピュータを、
入力データをブロック毎に符号化し、生成された符号化シンボルを外部記憶装置に蓄積する手段、
畳み込み符号化に必要な符号化シンボルを、上記外部記憶装置から最前段のメモリバッファに転送する手段、
各メモリバッファ内に配置された符号化シンボルを、次段のメモリバッファにシフトする手段、
最後段のメモリバッファ内に配置された符号化シンボルを、畳み込み符号化する手段、
として機能させることを特徴とする符号化プログラム。
【請求項７】
コンピュータを、
入力データを畳み込み復号化し、ブロック単位の符号化シンボルを生成する手段、
各符号化シンボルを、ブロック毎に外部記憶装置の異なるチャネルに出力する手段、
上記外部記憶装置内の符号化シンボルを、ブロック単位で復号化する手段、
として機能させることを特徴とする復号化プログラム。
【請求項８】
コンピュータを、
入力データを畳み込み復号化し、ブロック単位の符号化シンボルを生成する手段、
各符号化シンボルをブロック毎にメモリバッファに出力する手段、
ブロック毎に所定数の符号化シンボルが上記メモリバッファ内に蓄積された時点で、各符号化シンボルを外部記憶装置の一つのチャネルに出力する手段、
上記外部記憶装置内の符号化シンボルを、ブロック単位で復号化する手段、
として機能させることを特徴とする復号化プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は符号化技術及び復号化技術に係り、特に、デジタルデータを伝送するに際し、ブロック符号化及び畳み込み符号化による誤り訂正符号化を施す符号化技術と、このようにして符号化された伝送データに対して畳み込み復号化及びブロック復号化を施してデータを復元する技術に関する。
【０００２】
【従来の技術】
デジタル通信における誤り訂正符号技術の１つとして、フォーワードエラーコレクション（ＦＥＣ）がある。
これは、入力デジタルデータを所定のサイズに分割し、誤り訂正符号化をするブロック符号と、各ブロック符号化データを多重化する畳み込み符号との組み合わせで実現されるのが一般的である。
【０００３】
畳み込み符号化は、時刻ｔにおける符号化シンボルを時刻ｔ−ｋ＋１から時刻ｔまでのｋ個の情報を使って多重化する符号化方式であり、ここでｋを拘束長、出力符号数をｎとしたときのｋ／ｎを符号化率と呼ぶ。
畳み込み符号化において、入力となるそれぞれの符号化シンボルを別々の符号化ブロックに割り当てることにより、伝送パケットのバースト（局所集中的な）誤りに対応することができる。
【０００４】
このようなブロック符号や畳み込み符号の方式としては種々の方法が知られており、リードソロモン符号やビタビ符号はその代表例である。
また、米国特許６３７３４０６に代表されるようなチェーンリアクション符号と呼ばれる方式では、少ない計算量で符号化範囲を広げることが可能であり、大きなブロックサイズを実現できる方式として知られている。
【０００５】
【発明が解決しようとする課題】
しかしながら、従来の技術はいずれも、複数の符号化ブロックがプロセッサのレジスタ内またはメモリバッファ内に配置されていることを前提としており、メモリバッファ量を超える符号化ブロックの符号化および復号化をすることができない、という問題点がある。
例えば、畳み込み符号において拘束長ｋを別々の符号化ブロックから取得する場合、各符号化ブロックのサイズをｂとすれば、（ｋ＊ｂ）のメモリバッファが必要になる。
すなわちｋを小さく設定しても、ブロック符号のブロックサイズが増大するにつれて、少ないメモリ実装の処理装置では畳み込み符号を処理することができない。
【０００６】
この発明は、このような従来の問題点を解決するために案出されたものであり、メモリサイズに制約のある環境下においても、任意のブロックサイズの符号化シンボルを畳み込み符号化したり、ブロック復号化することが可能な技術を提供することを目的としている。
【０００７】
【課題を解決するための手段】
上記の目的を達成するため、請求項１に記載した符号化装置は、入力データをブロック毎に符号化し、生成された符号化シンボルを外部記憶装置に蓄積する手段と、畳み込み符号化に必要な符号化シンボルを、上記外部記憶装置からメモリバッファに転送する手段と、メモリバッファ内に配置された符号化シンボルを、畳み込み符号化する手段とを備えたことを特徴としている。
また、請求項５に記載した符号化プログラムは、コンピュータを、入力データをブロック毎に符号化し、生成された符号化シンボルを外部記憶装置に蓄積する手段、畳み込み符号化に必要な符号化シンボルを、上記外部記憶装置からメモリバッファに転送する手段、メモリバッファ内に配置された符号化シンボルを、畳み込み符号化する手段として機能させることを特徴としている。
【０００８】
このように、ブロック符号化されたデータ（チェーンリアクション符号化データを含む）を一時的に外部記憶装置内に蓄積した後、これらの中から伝送データを作成するために畳み込み演算が必要な入力シンボル部分のみを順次メモリに配置し、演算済み入力シンボルはメモリから削除することにより、メモリバッファ量を超えるブロック符号化データの畳み込み符号化が可能となる。
【０００９】
なお、この発明は特定の畳み込み符号化方式に限定されるものではく、あらゆる畳み込み符号化方式を採用可能である（以下同様）。
また、この発明における「畳み込み符号化」は、冗長度を付加することなく単にブロック符号を接合させる場合（単純な順次出力方式）をも含む概念である（以下同様）。
【００１０】
請求項２に記載した符号化装置は、入力データをブロック毎に符号化し、生成された符号化シンボルを外部記憶装置に蓄積する手段と、畳み込み符号化に必要な符号化シンボルを、上記外部記憶装置から最前段のメモリバッファに転送する手段と、各メモリバッファ内に配置された符号化シンボルを、次段のメモリバッファにシフトする手段と、最後段のメモリバッファ内に配置された符号化シンボルを、畳み込み符号化する手段とを備えたことを特徴としている。
また、請求項６に記載した符号化プログラムは、コンピュータを、入力データをブロック毎に符号化し、生成された符号化シンボルを外部記憶装置に蓄積する手段、畳み込み符号化に必要な符号化シンボルを、上記外部記憶装置から最前段のメモリバッファに転送する手段、各メモリバッファ内に配置された符号化シンボルを、次段のメモリバッファにシフトする手段、最後段のメモリバッファ内に配置された符号化シンボルを、畳み込み符号化する手段として機能させることを特徴としている。
【００１１】
上記「最前段のメモリバッファ」とは、外部記憶装置から符号化シンボルが転送されるメモリバッファを意味し、「最後段のメモリバッファ」とは、畳み込み符号化手段に符号化シンボルを供給するためのメモリバッファを意味する。
ここで、メモリバッファが３つ以上設けられている場合には、外部記憶装置から最前段のメモリバッファに転送された符号化シンボルは、途中に介装されたメモリバッファを経由し、最後段のメモリバッファにシフトされる。その間に、最前段のメモリバッファには、次の畳み込み符号化に必要な符号化シンボルが外部記憶装置から転送される。
これに対し、メモリバッファの数が２つの場合には、第１のメモリバッファが「最前段のメモリバッファ」に、また第２のメモリバッファが「最後段のメモリバッファ」に該当し、第１のメモリバッファ内の符号化シンボルが第２のメモリバッファにシフトされることとなる。
【００１２】
このように、外部記憶装置と畳み込み符号化手段との間に複数のメモリバッファを設け、外部記憶装置内の符号化シンボルを一のメモリバッファに一旦転送した後、他のメモリバッファに順次シフトさせ、最後段のメモリバッファから畳み込み符号化手段に符号化シンボルを供給することにより、メモリバッファ量を超えるブロック符号化データの畳み込み符号化が可能となると共に、外部記憶装置を介装させたことによるデータ転送速度の低下を補うことが可能となる。
【００１３】
請求項３に記載した復号化装置は、入力データを畳み込み復号化し、ブロック単位の符号化シンボルを生成する手段と、各符号化シンボルを、ブロック毎に外部記憶装置の異なるチャネルに出力する手段と、上記外部記憶装置内の符号化シンボルを、ブロック単位で復号化する手段とを備えたことを特徴としている。
また、請求項７に記載した復号化プログラムは、コンピュータを、入力データを畳み込み復号化し、ブロック単位の符号化シンボルを生成する手段、各符号化シンボルを、ブロック毎に外部記憶装置の異なるチャネルに出力する手段、上記外部記憶装置内の符号化シンボルを、ブロック単位で復号化する手段として機能させることを特徴としている。
【００１４】
このように、畳み込み符号化された伝送データを畳み込み復号化する際に、ディスク等の外部記憶装置に一旦出力した上で、ブロック復号化処理を順次行うことにより、メモリ量を超える符号化ブロック（チェーンリアクション符号化データを含む）の集合の復号化処理が可能となる。
【００１５】
請求項４に記載した復号化装置は、入力データを畳み込み復号化し、ブロック単位の符号化シンボルを生成する手段と、各符号化シンボルを、ブロック毎にメモリバッファに出力する手段と、ブロック毎に所定数の符号化シンボルが上記メモリバッファ内に蓄積された時点で、各符号化シンボルを外部記憶装置の一つのチャネルに出力する手段と、上記外部記憶装置内の符号化シンボルを、ブロック単位で復号化する手段とを備えたことを特徴としている。
また、請求項８に記載した復号化プログラムは、コンピュータを、入力データを畳み込み復号化し、ブロック単位の符号化シンボルを生成する手段、各符号化シンボルをブロック毎にメモリバッファに出力する手段、ブロック毎に所定数の符号化シンボルが上記メモリバッファ内に蓄積された時点で、各符号化シンボルを外部記憶装置の一つのチャネルに出力する手段、上記外部記憶装置内の符号化シンボルを、ブロック単位で復号化する手段として機能させることを特徴としている。
【００１６】
このように、畳み込み復号化された符号化シンボルをディスク等の外部記憶装置に蓄積するに際し、所定の出力メモリバッファを利用することにより、外部記憶装置へのアクセス回数および出力チャネル数を削減することが可能となり、復号化処理の高速化と外部記憶装置のチャネル数制約の回避が可能となる。
【００１７】
【発明の実施の形態】
図１は、この発明に係る符号化装置１０を示すブロック図である。この符号化装置１０は、複数のブロック符号化手段１２と、ハードディスク等の外部記憶装置１４と、メモリ転送手段１６と、メモリバッファ１８と、畳み込み符号化手段２０とを備えている。
【００１８】
この場合、入力データは任意のｖ個のブロックに分割され、ブロック符号化手段１２に入力される。畳み込み符号拘束長ｋのそれぞれのシンボルを、別々のブロック符号化シンボルに割り当てた場合を想定すれば、ｖ＝ｋとなる。
各ブロック符号化手段１２は、出力シンボルを外部記憶装置１４に書き出す。
メモリ転送手段１６は、外部記憶装置１４内に蓄積された各ブロックの符号化シンボルをｂづつ取り出し、メモリバッファ１８に転送する。
畳み込み符号化手段２０は、伝送回路２２から入力される伝送速度（ｒ）に基づき、メモリバッファ１８内の各符号化シンボルを順次畳み込み符号化し、伝送回路２２へ出力する。
【００１９】
メモリ転送手段１６が以下で述べる要件を満たすことにより、図１の符号化装置１０は、所定のメモリバッファ量で任意のブロック長で符号化されたシンボルを畳み込み符号化できる。
メモリ転送手段１６に要求される要件は、ブロック毎の出力シンボル数ｂで示すことができる。
【００２０】
ここで、１つのブロック符号化手段１２に要求されるメモリ消費量をｃ、符号化装置１０がブロック符号化に割り当てられるメモリサイズをｍとすると、各ブロック符号化手段１２が同時に動作できる数は  ｍ／ｃ  で示すことができる。
メモリバッファ１８の大きさをＭとすれば、シンボルサイズｓのとき、ｂの最大値ｍａｘ（ｂ）は（Ｍ／ｓ）／ｖとなる。
一方で、一回の畳み込み符号化に必要なシンボルはメモリバッファ１８内に配置されている必要があるため、ｂの最低必要量ｍｉｎ（ｂ）はｋ／ｖである。従ってｂは、
ｋ／ｖ≦ｂ≦（Ｍ／ｓ）／ｖ
を満たすことが要件となる。
【００２１】
一般に、外部記憶装置１４の入出力速度はメモリよりも遅いため、畳み込み符号手段２０へのシンボル供給が遅延する可能性が考えられる。
この問題を回避するためには、外部記憶装置１４と畳み込み符号化手段２０との間に複数のメモリバッファを設けると共に、一のメモリバッファ内のデータを他のメモリバッファにシフトする手段を設けることが有効である。
図２はその一例を示すものであり、第１のメモリバッファ１８ａと、第２のメモリバッファ１８ｂと、バッファシフト手段２４とを備えている。
【００２２】
この場合、メモリ転送手段１６は、まずシンボルｂ個をｖブロック分だけ第１のメモリバッファ１８ａに転送する。
つぎにメモリ転送手段１６は、畳み込み符号化手段２０からシンボル要求を受けた時点で、バッファシフト手段２４を使用して第１のメモリバッファ１８ａ内のシンボルをシフトして第２のメモリバッファ１８ｂ内に配置し、第１のメモリバッファ１８ａに再びシンボルｂ個をｖブロック分転送する。
【００２３】
畳み込み符号化手段２０は、第２のメモリバッファ１８ｂ内の各符号化シンボルを順次畳み込み符号化し、全てのシンボルを符号化し終わると、メモリ転送手段１６にシンボル要求を行う。
このとき、ｍａｘ（ｂ）は｛（Ｍ／２）／ｓ｝／ｖ、ｍｉｎ（ｂ）はｋ／ｖとなり、ｂは、
ｋ／ｖ≦ｂ≦｛（Ｍ／２）／ｓ｝／ｖ
を満たすことが要件となる。
【００２４】
３つ以上のメモリバッファを用いることにより、符号化シンボルの供給効率をさらに向上させることができる。
図３の実施形態にあっては、ｑ個（ｑ≧３）のメモリバッファを外部記憶装置１４と畳み込み符号化手段２０との間に設けている。
この場合、メモリ転送手段１６は、最前段に位置する第１のメモリバッファ１８ａにシンボルｂ個をｖブロック分転送する。また、畳み込み符号化手段２０からのシンボル要求に呼応し、バッファシフト手段２４を通じて符号化シンボルを次段のメモリバッファに順次シフトさせる。
そして、畳み込み符号化手段２０は、最後段に位置する第ｑのメモリバッファ１８ｑ内の符号化シンボルに対して畳み込み符号化処理を施す。
【００２５】
畳み込み符号化手段２０がメモリからシンボルを入力する速度Ｒは、伝送速度ｒと符号化率ｋ／ｎからＲ＝ｒ＊ｋ／ｎとなる。
【００２６】
図４は、この発明に係る第１の復号化装置３０を示すブロック図である。この第１の復号化装置３０は、畳み込み復号化手段３２と、外部記憶装置３４と、複数のブロック復号化手段３６とを備えている。
この場合、伝送回路３８から入力された誤り訂正符号化済みのデジタルデータは、畳み込み復号化手段３２において復号化され、各ブロック毎の符号化シンボルが生成される。これらの符号化シンボルは、外部記憶装置３４に出力される。
そして、外部記憶装置３４内に所定数の符号化シンボルが蓄積された後、ブロック復号化手段３６によって復号化処理が実行される。
この際、畳み込み復号化手段３２は、外部記憶装置３４にブロック毎の出力チャネルを作成する。ディスクファイルは、出力チャネルの実施形態の一例である。
【００２７】
ディスクファイルの例で説明すると、畳み込み復号化手段３２は、図１の入力ブロック数ｖに相当するディスクファイルを同時に作成し、拘束長ｋのシンボルを復号化する毎に、各ディスクファイルに該当シンボルを出力する。
各ディスクファイルに出力するシンボル数は、それぞれｋ／ｖである。
ブロック復号化手段３６は、畳み込み復号化手段３２からの通知または自己検出により、必要量の符号化シンボルがディスクファイルに蓄積されたことを受けて、復号処理を行う。
【００２８】
１つのブロック復号化手段３６に要求されるメモリ消費量をｃ、復号化装置３０がブロック復号に割り当てられるメモリサイズをｍとすると、各ブロック復号化手段３６が同時に動作できる数は  ｍ／ｃ  で示すことができる。
したがって、当該復号化装置３０がｍ≧ｃを満たしていれば、任意の拘束長ｋとブロック数を処理することが可能となる。
【００２９】
ここで、ディスクファイル等の外部記憶装置３４は、一般に性能面および機能面で下記の制約をうけることが多い。
▲１▼同時にオープンできるファイル数に上限がある。
▲２▼書き込み回数が多くなるほどシーク時間が増大し、性能が劣化する。
これに対処するため、図５に示すように、この発明に係る第２の復号化装置４０は、畳み込み復号化手段３２と外部記憶装置３４との間に、メモリバッファ４２と外部記憶出力手段４４を設けている。
【００３０】
この結果、畳み込み復号化手段３２で復号された各ブロックの符号化シンボルは、メモリバッファ４２に出力された後、外部記憶出力手段４４によって適切なタイミングで外部記憶装置３４に出力される。
ブロック復号化手段３６は、外部記憶装置３４に所定数の符号化シンボルが蓄積された後、復号化処理を実行する。
【００３１】
つぎに、この場合におけるメモリバッファ４２及び外部記憶装置３４内のデータ構造の一例を説明する。
すなわち、図６に示すように、メモリバッファ４２内には、それぞれｐ個の符号化シンボル４６が配列されたシンボルセット４８が、入力ブロック数に対応したｖ個分形成されている。
ここで、メモリバッファ４２の許容量をＭとすると、シンボルの配列数ｐはＭ／（ｖ＊シンボルサイズｓ）で与えられる。
【００３２】
外部記憶出力手段４４は、各シンボルセット４８にｐ個のシンボルが配置されたことを受けて、このデータ構造を外部記憶装置３４の１つの出力チャネルに順次書き出す。
出力チャネルがディスクファイルの場合、外部記憶出力手段４４は１つのファイル５０を外部記憶装置３４に作成し、シンボルセット４８の配列が完成する度にメモリバッファ４２内のデータ構造を当該ファイル５０に順次書き出す。
この結果、外部記憶装置３４には、メモリバッファ４２内に形成されたデータ構造全体の配列が形成される。
各ブロック復号化手段３６（＃１〜＃ｖ）は、ファイル５０内の該当するシンボルセットを順次読み込み、ブロック復号化処理を実行する。
【００３３】
このように、一旦メモリバッファ４２内に所定数の符号化シンボルからなるデータ構造を形成した後、外部記憶出力手段４４を介してまとめて外部記憶装置３４に書き出すようにすることで、外部記憶装置３４に対する書き込み回数を減らすことができ、全体の処理時間を短縮化することが可能となる。因みに、図６に示したデータ構造の例によれば、図４の実施形態のように畳み込み復号化手段３２から外部記憶装置３４に直接書き出す場合に比べ、書き込み回数は１／（ｐ＊ｖ）回に減少する。
また、外部記憶装置３４内に作成される出力ファイル数は、上記のように入力ブロック数にかかわらず１つで済むため、外部記憶装置３４のファイル数制約を考慮する必要がなくなる。
【００３４】
上記のブロック符号化手段１２、メモリ転送手段１６、畳み込み符号化手段２０、バッファシフト手段２４、畳み込み復号化手段３２、ブロック復号化手段３６、外部記憶出力手段４４は、コンピュータのＣＰＵが専用のアプリケーションプログラムを実行することによって実現される。
ただし、上記の各手段の機能を備えたＩＣを用意し、符号化装置１０、第１の復号化装置３０及び第２の復号化装置４０をハードウェア的に実現することも当然に可能である。
【００３５】
【発明の効果】
以上説明したように、請求項１の符号化装置及び請求項５の符号化プログラムによれば、少ないメモリ実装量の符号化装置であっても、任意のサイズのデジタルデータを畳み込み符号化することが可能となる。
また、請求項２の符号化装置及び請求項６の符号化プログラムによれば、メモリバッファ量を超えるブロック符号化データの畳み込み符号化が可能となると共に、外部記憶装置を介装させたことによるデータ転送速度の低下を補うことが可能となる。
また、請求項３の復号化装置及び請求項７の復号化プログラムによれば、比較的少量のメモリ使用にて復号化処理が可能となる。
さらに、請求項４の復号化装置及び請求項８の復号化プログラムによれば、外部記憶装置へのアクセス回数を減らして性能向上の効果が期待できると共に、外部記憶装置に生成するファイル数を１つに減らすことが可能になり、処理装置のファイル数制約を回避することができる。
【図面の簡単な説明】
【図１】この発明に係る符号化装置を示すブロック図である。
【図２】上記符号化装置の変形例を示すブロック図である。
【図３】上記符号化装置の他の変形例を示すブロック図である。
【図４】この発明に係る第１の復号化装置を示すブロック図である。
【図５】この発明に係る第２の復号化装置を示すブロック図である。
【図６】第２の復号化装置におけるメモリバッファ及び外部記憶装置内のデータ構造を示す概念図である。
【符号の説明】
１０  符号化装置
１２  ブロック符号化手段
１４  外部記憶装置
１６  メモリ転送手段
１８  メモリバッファ
１８ａ  第１のメモリバッファ
１８ｂ  第２のメモリバッファ
１８ｑ  第ｑのメモリバッファ
２０  畳み込み符号化手段
２４  バッファシフト手段
３０  第１の復号化装置
３２  畳み込み復号化手段
３４  外部記憶装置
３６  ブロック復号化手段
４０  第２の復号化装置
４２  メモリバッファ
４４  外部記憶出力手段
４６  符号化シンボル
４８  シンボルセット
５０  ファイル
【図１】
2004320650.tif 000003
【図２】
2004320650.tif 000004
【図３】
2004320650.tif 000005
【図４】
2004320650.tif 000006
【図５】
2004320650.tif 000007
【図６】
2004320650.tif 000008