(57)【要約】【課題】雑音等で改ざんされた信号を回復させる。【解決手段】劣化関数と、入力デジタル信号（２３）と、前置雑音除去システム（１２０）の出力の一連のシンボル（２４）とをメモリ（１１２、１１３、１１４）に格納する。劣化関数は、デジタル信号（２３）において、値Ｉを有するシンボルが値Ｊを有するシンボルで置き換えられると生じる信号劣化の尺度を与える。デジタル信号（２３）内のシンボル置き換えにより、処理済デジタル信号（２２）をコントローラ（１１１）により生成する。置き換えにより、劣化関数とシンボル（２４）で決定されるような、処理済デジタル信号（２２）内の全信号劣化の推定値が入力デジタル信号（２１）と比べて減少する場合には、入力デジタル信号（２３）内のそのシンボルのコンテクスト内の値Ｉを有する各シンボルを、値Ｊを有すシンボルで置き換える。【選択図】図１
2005210735.tif 000002
【特許請求の範囲】
【請求項１】
劣化関数と、チャネルによって改ざんされている入力デジタル信号を含む受信デジタル信号と、該受信デジタル信号を処理する前置雑音除去システムの出力を含む部分的に訂正された一連のシンボルとを記憶するためのメモリであって、前記劣化関数は、前記受信デジタル信号において、値Ｉを有するシンボルが値Ｊを有するシンボルによって置き換えられる場合に生じる信号劣化の尺度を与える、メモリと、
前記受信デジタル信号内のシンボルを置き換えることにより、前記受信デジタル信号から処理済デジタル信号を生成するコントローラと
を備える装置であって、
前記コントローラは、前記劣化関数および前記部分的に訂正された一連のシンボルを用いて決定されるような、前記処理済デジタル信号内の全信号劣化の推定値が、前記置き換によって前記入力デジタル信号と比べて減少する場合には、前記受信デジタル信号内の前記シンボルのコンテクスト内の値Ｉを有する各シンボルを、値Ｊを有すシンボルで置き換えることを特徴とする、信号処理装置。
【請求項２】
前記コントローラは、前記コンテクストの１つにおいて前記受信された信号内の前記シンボルの１つの実現値が前記部分的に訂正された一連のシンボル内の種々のシンボルによって置き換えられる頻度を決定することを特徴とする、請求項１に記載の信号処理装置。
【請求項３】
前記メモリはさらに、前記受信デジタル信号内の第１の長さの各部分系列の身元を有する第１のリストと、前記部分系列内の特定の場所にあるシンボルが前記部分的に訂正された一連のシンボル内の種々の他のシンボルによって置き換えられる回数を規定するテーブルとを記憶することを特徴とする、請求項１に記載の信号処理装置。
【請求項４】
前記受信デジタル信号から前記部分的に訂正された一連のシンボルを生成するための雑音除去システムをさらに備えることを特徴とする、請求項１に記載の信号処理装置。
【請求項５】
前記メモリはさらに、前記受信デジタル信号内の第２の長さの各部分系列の身元を有する第２のリストと、前記部分系列内の特定の場所にあるシンボルが前記部分的に訂正された一連のシンボル内の種々の他のシンボルによって置き換えられる回数を規定するテーブルとを記憶することを特徴とする、請求項３に記載の信号処理装置。
【請求項６】
前記コンテクストは前記第１のリストおよび前記第２のリストのうちの１つから選択され、該選択することは前記第１のリストおよび前記第２のリスト内の部分系列の前記出現回数に依存することを特徴とする、請求項５に記載の信号処理装置。
【請求項７】
チャネルによって改ざんされている入力デジタル信号を含む受信デジタル信号を処理して、処理済デジタル信号を生成するための信号処理方法であって、
前記受信デジタル信号を記憶すること、
前記受信デジタル信号を処理する前置雑音除去システムの出力を含む部分的に訂正された一連のシンボルを受信すること、
値Ｉを有するシンボルが値Ｊを有するシンボルによって置き換えられる場合に生じる信号劣化の尺度を与える信号劣化関数を規定する情報を記憶すること、および
前記置き換えることによって、前記劣化関数および前記部分的に訂正された一連のシンボルを用いて決定されるような、前記処理済デジタル信号内の全信号劣化の推定値が前記入力デジタル信号と比べて減少する場合には、前記受信デジタル信号内の前記シンボルのコンテクスト内の値Ｉを有する各シンボルを、値Ｊを有するシンボルで置き換えることにより、前記処理済デジタル信号を生成することを含むことを特徴とする、信号処理方法。
【請求項８】
全信号劣化の前記尺度は、前記コンテクストのうちの１つにおいて前記受信された信号内の前記シンボルのうちの１つの実現値が前記部分的に訂正された一連のシンボル内の種々のシンボルによって置き換えられる頻度に依存することを特徴とする、請求項７に記載の信号処理方法。
【請求項９】
前記受信デジタル信号内の第１の長さの各部分系列の身元を有する第１のリストと、前記部分系列内の特定の場所にあるシンボルが前記部分的に訂正された一連のシンボル内の種々の他のシンボルによって置き換えられる回数を規定するテーブルとを記憶することを含むことを特徴とする、請求項７に記載の信号処理方法。
【請求項１０】
前記受信デジタル信号から前記部分的に訂正された一連のシンボルを生成することをさらに含むことを特徴とする、請求項７に記載の信号処理方法。
【請求項１１】
前記受信デジタル信号内の第２の長さの各部分系列の身元を有する第２のリストと、各前記部分系列内の特定の場所にあるシンボルが前記部分的に訂正された一連のシンボル内の種々の他のシンボルによって置き換えられる回数を規定するテーブルとを記憶することをさらに含むことを特徴とする、請求項９に記載の信号処理方法。
【請求項１２】
前記コンテクストは前記第１のリストおよび前記第２のリストのうちの１つから選択され、該選択することは前記第１のリストおよび前記第２のリスト内の部分系列のための前記出現回数に依存することを特徴とする、請求項１１に記載の信号処理方法。
【請求項１３】
チャネルによって改ざんされている入力デジタル信号を含む受信された信号を処理して、処理済デジタル信号を生成するためのデータ処理プログラムで符号化されたコンピュータ読取り可能媒体であって、前記データ処理プログラムによって、データ処理システムが、
前記受信デジタル信号を記憶し、
前記受信デジタル信号を処理する前置雑音除去システムの出力を含む部分的に訂正された一連のシンボルを受信し、
値Ｉを有するシンボルが値Ｊを有するシンボルによって置き換えられる場合に生じる信号劣化の尺度を与える信号劣化関数を規定する情報を記憶し、
前記置き換えることによって、前記劣化関数および前記部分的に訂正された一連のシンボルを用いて決定されるような、前記処理済デジタル信号内の全信号劣化の推定値が前記入力デジタル信号と比べて減少する場合には、前記受信デジタル信号内の前記シンボルのコンテクスト内の値Ｉを有する各シンボルを、値Ｊを有するシンボルで置き換えることにより、前記処理済デジタル信号を生成することを特徴とする、コンピュータ読取り可能媒体。
【請求項１４】
全信号劣化の前記尺度は、前記コンテクストのうちの１つにおいて前記受信された信号内の前記シンボルのうちの１つの実現値が前記部分的に訂正された一連のシンボル内の種々のシンボルによって置き換えられる頻度に依存することを特徴とする、請求項１３に記載のコンピュータ読取り可能媒体。
【請求項１５】
前記データ処理システムはさらに、前記受信デジタル信号内の第１の長さの各部分系列の身元を有する第１のリストと、前記部分系列内の特定の場所にあるシンボルが前記部分的に訂正された一連のシンボル内の種々の他のシンボルによって置き換えられる回数を規定するテーブルとを記憶するようになされることを特徴とする、請求項１３に記載のコンピュータ読取り可能媒体。
【請求項１６】
前記データ処理システムはさらに、前記受信デジタル信号から前記部分的に訂正された一連のシンボルを生成するようになされることを特徴とする、請求項１３に記載のコンピュータ読取り可能媒体。
【請求項１７】
前記データ処理システムはさらに、前記受信デジタル信号内の第２の長さの各部分系列の身元を有する第２のリストと、前記部分系列内の特定の場所にあるシンボルが前記部分的に訂正された一連のシンボル内の種々の他のシンボルによって置き換えられる回数を規定するテーブルとを記憶するようになされることを特徴とする、請求項１５に記載のコンピュータ読取り可能媒体。
【請求項１８】
前記コンテクストは前記第１のリストおよび前記第２のリストのうちの１つから選択され、該選択することは前記第１のリストおよび前記第２のリスト内の部分系列のための前記出現回数に依存することを特徴とする、請求項１７に記載のコンピュータ読取り可能媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は信号処理に関し、より詳細には、信号の伝送あるいは処理によってその信号内に導入された誤りを訂正することに関する。
【背景技術】
【０００２】
本発明は、１つの簡単で例示的なシステムに関して、より容易に理解されることができると思われる。人がマイクロフォンに向かって話し、その出力がデジタル化され、その後、種々の電話線および交換システムを経由して相手に伝送される、電話による通話について考えてみる。通話相手の場所にあるスピーカが一連のデジタル値を受信し、その後、それが通話相手に対して再生される。一般的に、受信される信号系列は、伝送システム、デジタル／アナログ変換器およびアナログ／デジタル変換器によって誤りが導入されるために、送信される信号系列とは異なるであろう。たとえば、伝送システム内の雑音の結果として、伝送される信号系列のデジタル値のうちのある部分が変更されるようになる。雑音除去システムの１つの目的は、これらの雑音による誤りをできる限り除去することである。
【０００３】
先に説明された簡単な例は、広範な応用形態において直面する一般的な問題の一例である。一般的に、一連の「シンボル」からなる入力デジタル信号が、通信リンクを通して伝送され、その通信リンクの出力端において出力デジタル信号として受信される。その出力デジタル信号も一連の「シンボル」からなる。各シンボルは、アルファベットと呼ばれる、１組の所定のシンボルから選択される。その出力信号は、入力信号と同じアルファベットで書き表されるものと仮定される。
【０００４】
最も簡単な事例では、その信号は二値信号であり、その場合、アルファベットはシンボル「０」および「１」からなる。この事例では、入力および出力信号は一連の「０」および「１」からなる。しかしながら、一般的に他のアルファベットも用いられる。たとえば、各シンボルが０〜Ｍ−１の整数によって表されるデジタル化された信号が、デジタル加入者線（ＤＳＬ）を経由して、ユーザをインターネットに接続するためのブロードバンドデータ伝送システムにおいて一般的に用いられる。
【０００５】
上記の例は通信システムを参照するが、このタイプの雑音の問題は複数のデータ処理システムにおいて生じることに留意されたい。たとえば、データファイルを磁気ディスクドライブ上に記憶することは、通信リンク、すなわちディスクドライブを通してデジタル信号を伝送することと見なすことができる。その入力信号は一連のシンボル、たとえばバイトデータであり、それは所定のアルファベットから選択される。バイトデータの事例では、各シンボルは、データセット｛０，１，．．．，２５５｝から選択される整数値を有する。ディスクドライブから検索されるファイルも、このデータセットから選択される一連のシンボルからなる。入力信号シンボルは、ディスクドライブの電子回路によって処理され、局部的な磁界の形で記憶されており、出力信号を生成するために、その磁界が読み取られる。シンボルを磁界に、および磁界をシンボルに変換するデジタル／アナログ回路内の雑音によって、出力信号内に誤りが導入される。さらに、その磁界は、記憶中にランダムな事象によって変更される可能性があり、それによりさらに誤りが導入される。
【０００６】
同様に、デジタル写真も、信号を改ざん（あるいは汚染、破損）するチャネルを通して、信号を伝送することを伴うものと見なすことができる。この事例では、信号は画像であり、それは光検出器内の雑音によって改ざんされる。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明は、雑音等で改ざんされた信号の回復を目的とする。
【課題を解決するための手段】
【０００８】
本発明は、チャネルによって改ざんされている一連のシンボルを含む受信デジタル信号を処理して、処理済デジタル信号を生成するための方法および装置を含む。その方法は、受信デジタル信号を記憶すること、および、受信デジタル信号を処理する前置雑音除去システムの出力を含む、部分的に訂正された一連のシンボルを受信することを含む。値Ｉを有するシンボルが値Ｊを有するシンボルによって置き換えられる場合に生じる信号劣化の尺度（度合）を与える信号劣化関数を規定する情報を用いて、そのように置き換えることによって、劣化関数および部分的に訂正された一連のシンボルによって決定されるような、処理済デジタル信号内の全信号劣化の尺度が入力デジタル信号に比べて低減される場合には、受信デジタル信号内のそのシンボルのコンテクスト内の値Ｉを有する各シンボルを、値Ｊを有するシンボルで置き換えることにより処理済デジタル信号が生成される。その方法は、専用の装置において、あるいは汎用のデータ処理システムにおいて実施し得る。
【発明を実施するための最良の形態】
【０００９】
本発明は、あるデジタル信号が、雑音による誤りを導入するシステムによって処理されるときに、そのデジタル信号に導入される雑音に起因する信号劣化を低減するための方法を提供する。雑音を導入する処理システムは、その信号が送信される伝送チャネルに類似であるので、以下の説明では「チャネル」と呼ぶ。
【００１０】
ここで図１を参照すると、チャネル２０によって改ざんされている信号２３を処理する、本発明の一実施形態による雑音除去システム１００のブロック図が示される。そのチャネルは、既知のアルファベットからの一連のシンボルｙ1，ｙ2，．．．，ｙnを含む入力信号２１を処理して、同じくそのアルファベットからの一連のシンボルを含む出力信号２３を生成する。雑音を含む該出力信号は、系列ｚ1，ｚ2，．．．，ｚnによって示される。雑音を含む出力信号はまた、入力信号のアルファベットと同じアルファベットからのものであると仮定されている。すなわち、各シンボルは０〜Ｍ−１のうちの１つの値をとることができる。ただし、Ｍは１より大きな整数である。以下の説明を簡単にするために、シンボルの系列は括弧付きの文字によって示されるであろう。たとえば、信号系列ｙ1，ｙ2，．．．，ｙnは［ｙ］によって示される。
【００１１】
前置雑音除去システム１２０は［ｚ］を処理して、雑音が除去された信号の第１近似２４［ｒ］を受信している人にわからない方法で［ｚ］の系列の種々の要素を変更することにより、雑音を除去された信号の第１近似（部分的に訂正された一連のシンボル）２４、［ｒ］＝ｒ1，ｒ2，．．．，ｒnを生成すると仮定する。ｚqを中心にした２ｋ＋１個のシンボルの部分系列について考えてみる。ここでｋは整数である。ｋを選択する方法は以下においてさらに詳説する。この部分系列を［ｚ］（ｑ）で表す。すなわち、［ｚ］（ｑ）＝ｚq-k，ｚq-k+1，．．．，ｚq，ｚq+1，．．．，ｚq+kである。部分系列［ｚ］（ｑ）は、以下の説明において索引ｑの基準部分系列と呼ばれる場合もあるであろう。この部分系列が［ｚ］内の複数の場所において現われるようにｋが選択されるものと仮定される。すなわち、多くの相異なるｐの値について、［ｚ］（ｐ）＝［ｚ］（ｑ）である。本発明は、前置雑音除去システムがｚqの値を変更する場合には、出現する他の部分系列それぞれについても同じようにしてｚpの値を変更するという仮定に基づいている。
【００１２】
本発明は、前置雑音除去システムの出力を検査し、あるシンボルが誤って別のシンボルによって置き換えられるときに生じる信号劣化の尺度に基づいて、ｚqと、ｚpのそれぞれとに割り当てられる値を決定する。その際、この結果として生成される新たな系列２２、［ｚ’］が本発明からの出力である。本発明は、入力信号において値Ａを有するシンボルを出力信号において値Ｂを有するシンボルによって置き換えることにより、出力信号内に導入される劣化の尺度が定量化されていると仮定する。その劣化は、ＡおよびＢの値が異なると異なる場合がある。以下の説明では、この劣化の尺度（度合）を単に「劣化」と呼び、Ｃ（Ａ，Ｂ）によって表す。
【００１３】
３つ以上のシンボルを含むアルファベットを利用するシステムでは、Ｃ（Ａ，Ｂ）は多くの場合にＡとＢとの間の差に依存する。たとえば、アナログの時間変動信号を８ビットアナログ／デジタル変換器を用いて一連のデジタル値に変換することによって生成されるデジタル信号について考えてみる。結果として生成されるデジタル信号は、デジタル値０〜２５５に対応する２５６個のシンボルを有するアルファベットから選択される一連のシンボルである。出力信号は変換されてアナログ信号に戻され、聞き手に対して再生されるものと仮定する。あるシンボルが１だけ変更されることに起因する出力信号内の誤りは通常、あるシンボルが２だけ変更されることに起因する誤りよりもはるかに小さく、３以上の場合も同様である。それゆえ、劣化関数は、そのシンボルがこの事例において変更される量に依存する。
【００１４】
本発明がｚqの代わりに用いるための正しいシンボルを決定する態様は、図２を参照することによりさらに容易に理解することができ、図２はシンボル値を決定するために用いられる過程の流れ図である。このアルゴリズムは２つの部分に分けることができる。第１の部分では、［ｚ］（ｐ）＝［ｚ］（ｑ）となるｐを中心にした各部分系列が特定され、各ｐにつき、前置雑音除去システムがｒpに対して取り得る値を出力する回数が決定される。これら全てのｐの値について、ｒpが前置雑音除去システムによって値ｊを割り当てられた回数が、Ｎ（ｊ）によって表される。第１の部分を実施するアルゴリズムは、５１で示されるように、複数の変数を初期化することによって開始する。その後、このアルゴリズムは、［ｚ］（ｐ）＝［ｚ］（ｑ）となる各部分系列を探索する。ｐの現在の値に対して、このアルゴリズムは、５２で示されるように［ｚ］（ｐ）を検査する。［ｚ］（ｐ）＝［ｚ］（ｑ）である場合には、５３に示されるように、Ｎ（ｒp）がインクリメントされる。いずれの場合でも、５４に示されるように、つぎにｐはインクリメントされ、５５で示されるように、ｐの新たな値が、許容される範囲内に確実に入るかどうかが検査される。さらに多くの検査する部分系列が存在する場合には、その過程が繰り返される。全ての部分系列が検査されたときに、そのアルゴリズムは第２の部分に進む。
【００１５】
このアルゴリズムの第２の部分では、第１の部分からの計数値を用いて、劣化が推定される。該劣化は、ｚqが変更されて取り得るシンボル値に対する信号に帰する。ｚqが値Ｋに変更される事例について考えてみる。５６に示されるように、このアルゴリズムは、以下のように式（１）により劣化関数を用いて劣化推定値Ｄ（Ｋ）を計算する。
【００１６】
【数１】
2005210735.tif 000003
【００１７】
その後、このアルゴリズムは、Ｄ（Ｋ）が最小値を有するＫの値として定義されるＫminに等しくｚ’qを設定する。
【００１８】
このアルゴリズムが前置雑音除去システムの出力を変更する態様は、１つの簡単な例を参照することによりさらに容易に理解されることができる。誤りを生じるコストが全ての誤りについて同じである、すなわちＪとは異なる全てのＩについてＣ（Ｉ，Ｊ）＝Ｃ0である事例について考えてみる。全てのＩについてＣ（Ｉ，Ｉ）＝０であることに留意されたい。この場合に、Ｄ（Ｋ）はＳ（Ｋ）Ｃ0になる。ただし、Ｓ（Ｋ）は、Ｋとは異なるＪについてのＮ（Ｊ）の和である。ここで、１とは異なるＪについて、Ｎ（１）＞＞Ｎ（Ｊ）であるものと仮定する。すなわち、大抵の場合に、前置雑音除去システムは、雑音を含む信号において［ｚ］（ｑ）に等しい各部分系列の中央にあるシンボルを値１で置き換える。この場合に、Ｄ（Ｋ）はＫ＝１において最小値を有する。なぜなら、Ｄ（Ｋ）の他の全ての値はＳ（Ｋ）項にＮ（１）を含むことになるためである。それゆえ、この劣化関数の場合、本発明のアルゴリズムは、ｚ（ｐ）＝ｚ（ｑ）となる全てのｐについて、出力ｚ’pを、そのような索引ｐについてのｒp、すなわち前置雑音除去システムの出力の多数によってとられる値に設定する。
【００１９】
上記の実施形態は、処理されているシンボルを取り囲む２ｋ個の長い系列を利用して、２ｋ＋１個のシンボルの基準部分系列を定義しており、その基準部分系列の［ｚ］内の実現値および［ｒ］内の対応するシンボルが検査され、処理されているシンボルの代わりに用いられるべき出力シンボルを決定する。より一般的な事例に関する以下の説明を簡単にするために、処理されているシンボルのための「コンテクスト」を定義することが有用である。出力信号内の１つのシンボルについて考えてみる。固定された値を有し、そのシンボルに対して所定の場所にあるシンボルの部分系列が、そのシンボルのコンテクストと呼ばれる。先に記載される例では、シンボルｚqのコンテクストは、ｚqのそれぞれの側にあるｋ個のシンボルであった。ｚqの左側にあるｋ個のシンボルを［ａ］＝ａ1，ａ2，．．．，ａkによって、ｚqの右側にあるｋ個のシンボルを［ｂ］＝ｂ1，ｂ2，．．．，ｂkによって表す。その際、ｚqの代わりに置き換えられるシンボルを決定するために用いられる基準部分系列は［ｚ］（ｑ）＝［ａ］ｚq［ｂ］と書き表すことができる。しかし、他のコンテクストを本発明で利用してもよいことに留意されたい。たとえば、シンボルｚqで終わる系列、すなわち［ａ］ｚqを用いることができよう。同様に、ｚpで始まる系列、すなわちｚq［ｂ］を用いることができよう。さらに、系列［ａ］および［ｂ］の長さは異なることができよう。
【００２０】
さらに、系列［ａ］および／または［ｂ］が「ワイルドカード」を有するコンテクストも用いることができる。すなわち、［ａ］はａ1，ａ2，．．．，ａw，．．．，ａkの形で書き表されることができる。ただし、ａwには、あるシンボルのストリングを用いることができ、そのストリング内のシンボルは任意の値をとることができる。同様に、コンテクストのシンボルは、処理されているシンボルに対して所定の場所にある限り、処理されているシンボルに隣接して位置する必要はない。上記のシンボルのコンテクストの一般的な定義、およびそれによってもたらされる基準部分系列は、２次元画像データのような多次元信号にも当てはまる。
【００２１】
再び図１を参照する。本発明の一実施形態では、［ｚ］および［ｒ］が雑音除去システム１００によって読み取られる。［ｚ］系列は、受信される際にメモリ１１３に記憶される。ここで例示するために、各シンボルのコンテクストは、そのシンボルの左側にｋ個のシンボル、そのシンボルの右側にｋ’個のシンボルであるものと仮定される。第１のパスでは、コントローラ１１１が、シンボルが受信される際に、受信された系列［ｚ］をメモリ１１３に記憶する。コントローラ１１１はまた、［ｚ］内の長さＬ＝ｋ＋ｋ’＋１の全ての部分系列のリストを作成する。シンボルが受信される度に、コントローラ１１１は、［ｚ］内の直前に受信されたＬ個のシンボルを検査し、完成されたばかりの基準部分系列を決定する。［ｚ］系列内のｊ番目のシンボルが受信されたばかりであると仮定する。このシンボルは［ｚ］（ｊ−ｋ’−１）、すなわちｊ−ｋ’−１において処理されることになるシンボルに関連付けられる基準部分系列、を完成させる。
【００２２】
コントローラ１１１は、メモリ１１４に記憶される系列を検査し、［ｚ］（ｊ−ｋ’−１）が前に受信されていたか否かを決定する。受信されていなかった場合には、コントローラ１１１はメモリ１１４内にその部分系列のための新たなエントリを作成する。この系列のための前置雑音除去システム１２０からの結果を見失わないようにするために、そのエントリは、その部分系列を構成するＬ個のシンボルとＭ個のカウンタとを含む。その後、コントローラ１１１は、適当なカウンタ内に前置雑音除去システムの結果を記録する。すなわち、コントローラ１１１は、シンボル値ｒj-k'-1に対応するカウンタをインクリメントする。系列［ｚ］および［ｒ］の両方からの全てのシンボルが受信され、処理されたとき、第１のパスは終了する。
【００２３】
第２のパスでは、コントローラ１１１は、記憶された［ｚ］系列を順番に検査し、各シンボルを、図２を参照して先に説明されたアルゴリズムによって決定されるシンボルで置き換える。本発明の一実施形態では、劣化関数はメモリ１１２に記憶される。その系列の最初および最後には、コンテクストを定義するには不十分なデータしか存在しない。それゆえ、最初のｋ個のシンボルおよび最後のｋ’個のシンボルは、前置雑音除去システムからの［ｒ］系列内の対応するシンボルに設定される。
【００２４】
受信された信号［ｚ］および［ｒ］は高速メモリに記憶される必要はないことに留意されたい。第１のパス中のコントローラ１１１は常時、［ｚ］からのＬ個のシンボルと、［ｒ］から１つのみのシンボルとを必要とする。それゆえ、受信された信号は、現時点で用いられているＬ個のシンボルを記憶するための小さなバッファを除いて、ディスクドライブ上に記憶できる。コンテクストメモリ１１４だけは高速メモリである必要がある。
【００２５】
上記の例は、Ｌの値が決定されていると仮定している。本発明は、受信された系列［ｚ］が統計的に有意な回数だけ繰り返される基準部分系列を有し、任意のそのような基準部分系列に対応する計数値によって、前置雑音除去システムの挙動の特性が正確に導かれるようになる事例において、最も大きな利点を提供する。受信された系列内に基準部分系列が出現するのが観察される回数が少ない場合には、先に説明されたＮ（Ｊ）計数値の確度が低い可能性があり、それゆえ、推定値Ｄ（Ｋ）の確度も同様に低くなろう。これらの計数値の確度が著しく低い場合には、正しい出力シンボルに関して誤った判断がなされるであろう。
【００２６】
基準部分系列が出現する回数は、コンテクストの長さにある程度依存する。上記のようにして処理されるべきシンボルｚが、長さＬ−１のコンテクストを有する事例について考えてみる。さらに、対応する基準部分系列［ａ］ｚ［ｂ］がＱ回（ただし、Ｑ＞＞１かつＱ／Ｍ＞＞１）現われるが、それよりも長い基準部分系列ｔ［ａ］ｚ［ｂ］は、ｔの任意の値で、頻繁には現われないものと仮定する。その際、Ｌよりも長い基準部分系列は出現する回数がはるかに少なくなり、それよりも小さなコンテクストが用いられた事例に対して、計数値の統計的確度が劣化するであろう。それゆえ、Ｌに対してあまりにも大きな値を選択すると、結果として判断を誤る可能性が高くなる。
【００２７】
任意の固定されたＬの場合、そのシステムは、入力信号においてＬ個以下のサンプルの中の相関しか利用することができない。実効的に利用することができる入力相関の範囲が広くなると、性能が改善される。先に検討したこととは対照的に、これは、Ｌを小さくしすぎるのはよくないという主張である。
【００２８】
上記の説明から、Ｌの最適値が存在することが明らかである。この最適値は経験的に決定されることができる。入力信号内の相関をとられる系列の長さが、時間が経過しても著しく変化しない場合には、Ｌのための最適値は、代表的な入力信号を利用し、Ｌの種々の値に対する雑音除去の結果を比較することにより、実験的に決定されることができる。
【００２９】
原理的には、Ｌは、任意の特定の出力信号を得るために、複数の異なるＬ値を用いて信号の雑音を除去することにより決定されることができる。そのようなシステムでは、Ｌの値は、統計的に満足のいく確度を与える値が見つかるまで、ある上限値から減少させることができる。適度なＬの開始値は［ｌｏｇ（ｎ）／ｌｏｇ（Ｍ）］によって与えられる。ただしｎは［ｚ］系列内のシンボルの数であり、Ｍはアルファベット内のシンボルの数である。
【００３０】
ここで図３を参照すると、第２のパスにおいて用いられる信号処理アルゴリズムの流れ図が示される。受信された信号がメモリ１１３に記憶された後に、コントローラ１１１は、受信されたシンボルを順番に検査し、あるシンボルが別の値に設定し直されるべきであるか否かを決定する。コントローラ１１１がｚjにあるとき、コントローラ１１１は、ｚjの左側においてｋ個のシンボルを、ｚjの右側においてｋ’個のシンボルを読み取り、１５１で示されるように、その計数値がメモリ１１４に記憶されているｚjのための最も長い基準部分系列［ｚ］（ｊ）を決定する。コントローラ１１１は、１５２で示されるように、メモリ１１４からこの基準部分系列に関連付けられる計数値を引き出し、１５３で示されるように、記憶された計数値が続行のための十分な統計的確度を有するか否かを決定する。その計数値が十分な確度を有する場合には、コントローラ１１１は［ｚ］（ｊ）とともに記憶される計数値を読み取り、１５５で示されるように、先に説明された式（１）を用いて、ｚjがそれぞれ取り得るシンボル値によって置き換えられる場合に生じていたであろう信号劣化を推定する。その後、１５６で示されるように、そのシンボルは、劣化が最小限に抑えられた値に設定される。
【００３１】
この基準部分系列のための計数値の統計的確度が低すぎる場合には、１５８で示されるように、コントローラ１１１はさらに小さなコンテクストを探索する。そのようなコンテクストが存在する場合には、関連する基準部分系列が選択され、１６０および１５２で示されるように、その過程が繰り返される。さらに小さなコンテクストが入手できない場合には、１５９で示されるように、ｚ’jがｒj、すなわち前置雑音除去システムによって与えられる値に設定される。１５７で示されるようにｊをインクリメントし、処理されることになる全てのシンボルが処理されるまで、その過程を繰り返すことにより、その過程が続けられる。先に述べられたように、コンテクストを有するにはあまりにも端に近すぎる、系列［ｚ’］の端にあるシンボルは、系列［ｒ］内の対応する場所にある値に設定される。
【００３２】
本発明の先に記載された実施形態は、受信された信号を直に処理し、種々のパラメータ、コンテクストおよび劣化関数を記憶する際に用いるための特定のメモリを有する雑音除去装置を利用してきた。しかしながら、本発明は汎用のデータ処理システム上で実施されることもでき、そのデータ処理システム内に適当なデータ処理プログラムをロードすることにより、チャネルから受信された信号のコピーおよび前置雑音除去システムの出力のコピーがそのデータ処理システムに転送される。前置雑音除去システムが同じデータ処理システムにおいて動作する実施形態も実施することができる。
【００３３】
先に記載された実施形態は、劣化関数、コンテクストのリストおよび受信された信号を記憶するために個別のメモリを用いる。しかしながら、これらの量のうちの２つ以上を記憶するために単一のメモリが用いられる実施形態も、本発明の教示から逸脱することなく構成されることができる。したがって、先に説明された個別のメモリには、より大きなメモリの一部を用いることができることは理解されたい。
【００３４】
これまでの説明および添付図面から、本発明に対する種々の変更が当業者には明らかになるであろう。したがって、本発明は、添付の特許請求の範囲によってのみ制限されるべきである。以下に本発明の実施態様の一部を例示して本発明の実施の参考に供する。
【００３５】
（実施態様１）：劣化関数と、チャネルによって改ざんされている入力デジタル信号を含む受信デジタル信号と、該受信デジタル信号を処理する前置雑音除去システムの出力を含む部分的に訂正された一連のシンボルとを記憶するためのメモリであって、前記劣化関数は、前記受信デジタル信号において、値Ｉを有するシンボルが値Ｊを有するシンボルによって置き換えられる場合に生じる信号劣化の尺度を与える、メモリと、前記受信デジタル信号内のシンボルを置き換えることにより、前記受信デジタル信号から処理済デジタル信号を生成するコントローラとを備える装置であって、前記コントローラは、前記劣化関数および前記部分的に訂正された一連のシンボルを用いて決定されるような、前記処理済デジタル信号内の全信号劣化の推定値が、前記置き換によって前記入力デジタル信号と比べて減少する場合には、前記受信デジタル信号内の前記シンボルのコンテクスト内の値Ｉを有する各シンボルを、値Ｊを有すシンボルで置き換えることを特徴とする、信号処理装置。
【００３６】
（実施態様２）：前記コントローラは、前記コンテクストの１つにおいて前記受信された信号内の前記シンボルの１つの実現値が前記部分的に訂正された一連のシンボル内の種々のシンボルによって置き換えられる頻度を決定することを特徴とする、実施態様１に記載の信号処理装置。
【００３７】
（実施態様３）：前記メモリはさらに、前記受信デジタル信号内の第１の長さの各部分系列の身元を有する第１のリストと、前記部分系列内の特定の場所にあるシンボルが前記部分的に訂正された一連のシンボル内の種々の他のシンボルによって置き換えられる回数を規定するテーブルとを記憶することを特徴とする、実施態様１に記載の信号処理装置。
【００３８】
（実施態様４）：前記受信デジタル信号から前記部分的に訂正された一連のシンボルを生成するための雑音除去システムをさらに備えることを特徴とする、実施態様１に記載の信号処理装置。
【００３９】
（実施態様５）：前記メモリはさらに、前記受信デジタル信号内の第２の長さの各部分系列の身元を有する第２のリストと、前記部分系列内の特定の場所にあるシンボルが前記部分的に訂正された一連のシンボル内の種々の他のシンボルによって置き換えられる回数を規定するテーブルとを記憶することを特徴とする、実施態様３に記載の信号処理装置。
【００４０】
（実施態様６）：前記コンテクストは前記第１のリストおよび前記第２のリストのうちの１つから選択され、該選択することは前記第１のリストおよび前記第２のリスト内の部分系列の前記出現回数に依存することを特徴とする、実施態様５に記載の信号処理装置。
【００４１】
（実施態様７）：チャネルによって改ざんされている入力デジタル信号を含む受信デジタル信号を処理して、処理済デジタル信号を生成するための信号処理方法であって、前記受信デジタル信号を記憶すること、前記受信デジタル信号を処理する前置雑音除去システムの出力を含む部分的に訂正された一連のシンボルを受信すること、値Ｉを有するシンボルが値Ｊを有するシンボルによって置き換えられる場合に生じる信号劣化の尺度を与える信号劣化関数を規定する情報を記憶すること、および、前記置き換えることによって、前記劣化関数および前記部分的に訂正された一連のシンボルを用いて決定されるような、前記処理済デジタル信号内の全信号劣化の推定値が前記入力デジタル信号と比べて減少する場合には、前記受信デジタル信号内の前記シンボルのコンテクスト内の値Ｉを有する各シンボルを、値Ｊを有するシンボルで置き換えることにより、前記処理済デジタル信号を生成することを含むことを特徴とする、信号処理方法。
【００４２】
（実施態様８）：全信号劣化の前記尺度は、前記コンテクストのうちの１つにおいて前記受信された信号内の前記シンボルのうちの１つの実現値が前記部分的に訂正された一連のシンボル内の種々のシンボルによって置き換えられる頻度に依存することを特徴とする、実施態様７に記載の信号処理方法。
【００４３】
（実施態様９）：前記受信デジタル信号内の第１の長さの各部分系列の身元を有する第１のリストと、前記部分系列内の特定の場所にあるシンボルが前記部分的に訂正された一連のシンボル内の種々の他のシンボルによって置き換えられる回数を規定するテーブルとを記憶することを含むことを特徴とする、実施態様７に記載の信号処理方法。
【００４４】
（実施態様１０）：前記受信デジタル信号から前記部分的に訂正された一連のシンボルを生成することをさらに含むことを特徴とする、実施態様７に記載の信号処理方法。
【００４５】
（実施態様１１）：前記受信デジタル信号内の第２の長さの各部分系列の身元を有する第２のリストと、各前記部分系列内の特定の場所にあるシンボルが前記部分的に訂正された一連のシンボル内の種々の他のシンボルによって置き換えられる回数を規定するテーブルとを記憶することをさらに含むことを特徴とする、実施態様９に記載の信号処理方法。
【００４６】
（実施態様１２）：前記コンテクストは前記第１のリストおよび前記第２のリストのうちの１つから選択され、該選択することは前記第１のリストおよび前記第２のリスト内の部分系列のための前記出現回数に依存することを特徴とする、実施態様１１に記載の信号処理方法。
【００４７】
（実施態様１３）：チャネルによって改ざんされている入力デジタル信号を含む受信された信号を処理して、処理済デジタル信号を生成するためのデータ処理プログラムで符号化されたコンピュータ読取り可能媒体であって、前記データ処理プログラムによって、データ処理システムが、前記受信デジタル信号を記憶し、前記受信デジタル信号を処理する前置雑音除去システムの出力を含む部分的に訂正された一連のシンボルを受信し、値Ｉを有するシンボルが値Ｊを有するシンボルによって置き換えられる場合に生じる信号劣化の尺度を与える信号劣化関数を規定する情報を記憶し、前記置き換えることによって、前記劣化関数および前記部分的に訂正された一連のシンボルを用いて決定されるような、前記処理済デジタル信号内の全信号劣化の推定値が前記入力デジタル信号と比べて減少する場合には、前記受信デジタル信号内の前記シンボルのコンテクスト内の値Ｉを有する各シンボルを、値Ｊを有するシンボルで置き換えることにより、前記処理済デジタル信号を生成することを特徴とする、コンピュータ読取り可能媒体。
【００４８】
（実施態様１４）：全信号劣化の前記尺度は、前記コンテクストのうちの１つにおいて前記受信された信号内の前記シンボルのうちの１つの実現値が前記部分的に訂正された一連のシンボル内の種々のシンボルによって置き換えられる頻度に依存することを特徴とする、実施態様１３に記載のコンピュータ読取り可能媒体。
【００４９】
（実施態様１５）：前記データ処理システムはさらに、前記受信デジタル信号内の第１の長さの各部分系列の身元を有する第１のリストと、前記部分系列内の特定の場所にあるシンボルが前記部分的に訂正された一連のシンボル内の種々の他のシンボルによって置き換えられる回数を規定するテーブルとを記憶するようになされることを特徴とする、実施態様１３に記載のコンピュータ読取り可能媒体。
【００５０】
（実施態様１６）：前記データ処理システムはさらに、前記受信デジタル信号から前記部分的に訂正された一連のシンボルを生成するようになされることを特徴とする、実施態様１３に記載のコンピュータ読取り可能媒体。
【００５１】
（実施態様１７）：前記データ処理システムはさらに、前記受信デジタル信号内の第２の長さの各部分系列の身元を有する第２のリストと、前記部分系列内の特定の場所にあるシンボルが前記部分的に訂正された一連のシンボル内の種々の他のシンボルによって置き換えられる回数を規定するテーブルとを記憶するようになされることを特徴とする、実施態様１５に記載のコンピュータ読取り可能媒体。
【００５２】
（実施態様１８）：前記コンテクストは前記第１のリストおよび前記第２のリストのうちの１つから選択され、該選択することは前記第１のリストおよび前記第２のリスト内の部分系列のための前記出現回数に依存することを特徴とする、実施態様１７に記載のコンピュータ読取り可能媒体。
【図面の簡単な説明】
【００５３】
【図１】本発明の一実施形態による雑音除去システムのブロック図である。
【図２】シンボル値を決定するために用いられる過程の流れ図である。
【図３】第２のパスにおいて用いられる信号処理アルゴリズムの流れ図である。
【符号の説明】
【００５４】
２０  チャネル
２１  入力デジタル信号
２２  処理済デジタル信号
２３  受信デジタル信号
２４  部分的に訂正された一連のシンボル
１００  雑音除去システム
１１１  コントローラ
１１２  メモリ（劣化関数）
１１３  メモリ（［ｚ］系列）
１１４  メモリ（コンテクストメモリ）
１２０  前置雑音除去システム
【図１】
2005210735.tif 000004
【図２】
2005210735.tif 000005
【図３】
2005210735.tif 000006