(57)【要約】  本発明は、ユーザ・データ・ストリーム(m)をチャネル・データ・ストリーム(y)に符号化する符号化装置及び符号化方法、並びに、対応する復号化装置及び復号化方法に関する。記憶システムの、最悪のケースのBER特性を改良し、信頼度を向上させる（特に2次元光記憶システムにおいて、又は通信システムにおいて、特に、情報レートの大きな損失なしでBERが確実に低くなるようにする）ために、符号化装置を本発明によって提案する。この符号化装置は、ユーザ・データ・ストリーム(m)よりもシンボルが少なくとも１つ多い中間データ・ストリーム(i)にユーザ・データ・ストリーム(m)を変換する拡張装置と、中間データ・ストリーム(i)を用いてスクランブル・ストリーム(c)のフィギュア・オブ・メリットの値(v)を、スクランブル符号(C)からのスクランブル・ストリーム(c)毎に反復的に判定する処理装置（100、200、500、600）と、最適メリット値（v_opt）をメリット値(v)から選択し、フィギュア・オブ・メリットが最適メリット値（v_opt）に等しい最適スクランブル・ストリーム（c  opt）を選択する選択装置（300）と、最適スクランブル・ストリーム(c  opt)のシンボルを、中間データ・ストリームの対応するシンボルにマッピングして、チャネルに出力するためのチャネル・データ・ストリーム(y)を得る少なくとも１つのマッピング装置（400）とを備える。
2008502085.tif 000002
【特許請求の範囲】
【請求項１】
ユーザ・データ・ストリームをチャネル・データ・ストリームに符号化する符号化装置であって、
前記ユーザ・データ・ストリームよりもシンボルが少なくとも1つ多い中間データ・ストリームに前記ユーザ・データ・ストリームを変換する拡張装置と、
スクランブル符号からスクランブル・ストリーム毎に、前記中間データ・ストリームを用いて前記スクランブル・ストリームのフィギュア・オブ・メリットの値を、反復的に判定する処理装置であって、スクランブル・ストリームは、前記中間データ・ストリームと等しく多いシンボルを備え、前記フィギュア・オブ・メリットが、前記スクランブル・ストリームの部分の収集体にわたる和であり、前記部分が、前記スクランブル・ストリームからの少なくとも２つのシンボル位置を備え、前記和の各項が、前記中間ストリームの対応部分を用いた、前記スクランブル・ストリームの前記部分のフィギュア・オブ・メリットであり、前記スクランブル・ストリームの前記部分のそれぞれにおいて、シンボルの考えられる組み合わせそれぞれが、前記スクランブル符号からの、等しく多いスクランブル・ストリームにおいて生じる処理装置と、
前記メリット値から、最適メリット値を選択し、前記フィギュア・オブ・メリットが前記最適メリット値に等しい最適なスクランブル・ストリームを選択する選択装置と、
前記中間データ・ストリームの対応シンボルに、前記最適なスクランブル・ストリームのシンボルをマッピングして、チャネルに出力するために、前記チャネル・データ・ストリームを得る少なくとも１つのマッピング装置とを備えることを特徴とする符号化装置。
【請求項２】
請求項１記載に符号化装置であって、
前記少なくとも１つのマッピング装置は、前記中間データ・ストリームの前記対応シンボルにスクランブル・ストリームのシンボルをマッピングするよう動作するものであり、前記処理装置は、前記中間データ・ストリームの前記対応シンボルに前記スクランブル・ストリームの前記シンボルの前記マッピングからの結果を用いることにより、前記フィギュア・オブ・メリットの前記メリット値をスクランブル・ストリーム毎に判定するよう動作することを特徴とする符号化装置。
【請求項３】
請求項１記載の符号化装置であって、
前記少なくとも１つのマッピング装置は、前記スクランブル・ストリームの前記シンボルを前記中間データ・ストリームの前記対応シンボルに加えることによって前記中間データ・ストリームの前記対応シンボルにスクランブル・ストリームのシンボルをマッピングする手段を備えることを特徴とする符号化装置。
【請求項４】
請求項１記載の符号化装置であって、
前記スクランブル符号が反復符号であることを特徴とする符号化装置。
【請求項５】
請求項４記載の符号化装置であって、
前記処理装置は、少なくとも２つのヒストグラムから前記チャネル・データ・ストリームの前記部分の前記メリット値の前記和を判定するよう動作するものであり、各ヒストグラムが、前記中間データ・ストリームの前記部分のいくつかにおいてシンボルの組み合わせの生起の頻度を格納することを特徴とする符号化装置。
【請求項６】
請求項１記載の符号化装置であって、
前記チャネル・ストリームが1次元データ・ストリームであり、前記部分はそれぞれ、一定数の後続シンボルを、特に、3乃至８ビットの範囲で備えることを特徴とする符号化装置。
【請求項７】
請求項１記載の符号化装置であって、
前記チャネル・データ・ストリームが2次元データ・ストリームであり、前記チャネル・データは、2次元格子の無限範囲のストリップに沿った第１の方向において、かつ、前記第１の方向にほぼ直交する第２の方向における有限範囲のものであり、前記ストリップは、前記第２の方向に沿って互いに重ねられたいくつかのシンボル行を備え、前記部分それぞれが、一定数のシンボルを備えることを特徴とする符号化装置。
【請求項８】
請求項７記載の符号化装置であって、
前記シンボルが、疑似正方形格子、疑似矩形格子又は6角形格子の格子点上に配置されることを特徴とする符号化装置。
【請求項９】
請求項８記載の符号化装置であって、
前記部分それぞれは、前記６角形格子の格子点上に配置された７つのシンボルを備え、各ユーザ部分が、中央ユーザ・シンボル、及び最も近い６つの近傍シンボルを備えることを特徴とする符号化装置。
【請求項１０】
請求項１記載の符号化装置であって、
前記拡張装置は、少なくとも１つのシンボルを前記ユーザ・データ・ストリームに付加することによって前記ユーザ・データ・ストリームを前記中間データ・ストリームに変換するよう動作するものであり、前記少なくとも１つのシンボルの値は、前記符号器及び前記復号器に知られており、考えられるユーザ・データ・ストリーム全てについて同じであることを特徴とする符号化装置。
【請求項１１】
請求項１記載の符号化装置であって、
前記拡張装置は、誤り訂正符号からの語である中間ストリームに前記ユーザ・データ・ストリームを変換するよう動作するものであり、前記スクランブル符号は、前記誤り訂正符号のサブ符号のコセットであり、前記誤り訂正符号からの語である前記中間ストリームに前記スクランブル符号からのスクランブル・ストリームをマッピングした結果であることを特徴とする符号化装置。
【請求項１２】
ユーザ・データ・ストリームをチャネル・データ・ストリームに符号化する符号化方法であって、
前記ユーザ・データ・ストリームよりもシンボルが少なくとも1つ多い中間データ・ストリームに前記ユーザ・データ・ストリームを変換する工程と、
スクランブル符号からスクランブル・ストリーム毎に、前記中間データ・ストリームを用いて前記スクランブル・ストリームのフィギュア・オブ・メリットの値を反復的に判定する工程であって、スクランブル・ストリームは、前記中間データ・ストリームと等しく多いシンボルを備え、前記フィギュア・オブ・メリットが、前記スクランブル・ストリームの部分の収集体にわたる和であり、前記部分が、前記スクランブル・ストリームからの少なくとも２つのシンボル位置を備え、前記和の各項が、前記中間ストリームの対応部分を用いた、前記スクランブル・ストリームの前記部分のフィギュア・オブ・メリットであり、前記スクランブル・ストリームの前記部分のそれぞれにおいて、シンボルの考えられる組み合わせそれぞれが、前記スクランブル符号からの、等しく多いスクランブル・ストリームにおいて生じる工程と、
前記メリット値から、最適メリット値を選択し、前記フィギュア・オブ・メリットが前記最適メリット値に等しい最適なスクランブル・ストリームを選択する工程と、
前記中間データ・ストリームの対応シンボルに、前記最適なスクランブル・ストリームのシンボルをマッピングして、チャネルに出力するために、前記チャネル・データ・ストリームを得る工程とを備えることを特徴とする符号化方法。
【請求項１３】
請求項１１記載の方法によってユーザ・データ・ストリームが符号化されるチャネル・データ・ストリームを復号化する復号化装置であって、
前記誤り訂正符号のチャネル符号語に前記チャネル・データ・ストリームを復号化するECC復号化装置と、
前記中間データ・ストリームに前記スクランブル符号語をマッピングすることによって前記チャネル符号語が生じるように前記チャネル符号語から中間データ・ストリーム及びスクランブル符号語を見つける分離装置と、
前記ユーザ・データ・ストリームよりも少なくとも１つ多いシンボルを備える中間データ・ストリームに前記ユーザ・データ・ストリームを拡張することによって前記中間データ・ストリームが生じるように前記中間データ・ストリームからユーザ・データ・ストリームを取り出すマッピング解除装置とを備えることを特徴とする復号化装置。
【請求項１４】
請求項１１記載の方法によってユーザ・データ・ストリームが符号化されるチャネル・データ・ストリームを復号化する復号化方法であって、
前記誤り訂正符号のチャネル符号語に前記チャネル・データ・ストリームを復号化する工程と、
前記中間データ・ストリームに前記スクランブル符号語をマッピングすることによって前記チャネル符号語が生じるように前記チャネル符号語から中間データ・ストリーム及びスクランブル符号語を見つける工程と、
前記ユーザ・データ・ストリームよりも少なくとも１つ多いシンボルを備える中間データ・ストリームに前記ユーザ・データ・ストリームを拡張することによって前記中間データ・ストリームが生じるように前記中間データ・ストリームからユーザ・データ・ストリームを取り出す工程とを備えることを特徴とする復号化方法。
【請求項１５】
記録担体であって、請求項1記載の符号化方法によってユーザ・データ・ストリームが符号化されるチャネル・データ・ストリームを記憶することを特徴とする記録担体。
【請求項１６】
信号であって、請求項１記載の符号化方法によってユーザ・データ・ストリームが符号化されるチャネル・データ・ストリームを担持することを特徴とする信号。
【請求項１７】
コンピュータ・プログラムであって、該コンピュータ・プログラムがコンピュータ上で実行されると、請求項１２又は１４に記載の方法の工程をコンピュータに行わせるプログラム・コード手段を備えることを特徴とするコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ユーザ・データ・ストリームをチャネル・データ・ストリームに符号化する、符号化装置、及び方法に関する。本発明は、対応する復号化装置及び復号化方法と、本発明によって符号化されたデータを担持する記録担体及び信号と、前述の方法を実施するコンピュータ・プログラムとに更に関する。
【背景技術】
【０００２】
2次元光記憶システム（特に、2次元チャネル・データ・ストリームの符号化及び復号化を行う方法）は、欧州特許出願第02076665.5号（PHNL020368）に記載されている。2次元光記憶の目的は、同じ物理的読み出しシステム（波長、開口数）を用いて、より高い（例えば、ブルーレイ・ディスク（BD）よりも２倍大きい）記憶密度を達成することである。想定された2次元光記憶システムの要素の１つは、光媒体上のビット（複数値シンボル）に2次元の6角形格子を用いることである。よって、各ビット（シンボル）は最も近い６つの近傍を有する。最も近い近傍ビットのみが関係する第１のシェル近似では、2次元指数iを備えた特定の入力ビットxiよりも読み出し場所が上の場合のチャネル出力は、この入力ビットと、それに最も近い６つの近傍ビットであって１に等しいビットの数との関数である。この数をziと呼ぶ。
【０００３】
図１は、10xi+ziの関数としてチャネル出力の第１のシェル近似を示す。よって、６つのゼロ・ビットによってゼロ・ビットが取り囲まれているケースは、図中の曲線の最も左の点に対応する。同様に、１のビット６つによって１のビットが取り囲まれているケースは、図中の曲線の最も右の点に対応する。図２には、7ビット6角形クラスタの種々のクラスタ・タイプを示す。
【０００４】
ビット誤りレート（BER）は、チャネル入力フィールドと呼ばれる、チャネル入力xの系列（2次元格子）によって変わってくるものであり、チャネル入力フィールドが全て１を備える場合に最悪である。その場合、（平均）ビット誤りレート（BER）は、通常のランダムな入力メッセージよりもずっと悪い。相加性白色ガウス雑音（AWGN）チャネル・モデルを用いる場合、入力フィールド全てにわたる、BERの最悪ケースは、別々の２つの（雑音なしの）チャネル出力フィールド間の最小二乗ユークリッド距離によって定められる。
【０００５】
同じ物理的読み出し特性を用いる一方で記憶密度が１次元光記憶の記憶密度を超える２次元光記憶の場合、最も近い６つの近傍ビットが全て１であり、中央ビットがゼロ又は１であり、更に外側の全ビットが全て１であるチャネル入力フィールド対の場合に、別々のチャネル出力フィールド間の最小二乗ユークリッド距離が生起する。このことは、図１中の曲線上のz番目の点と10+z番目の点（z=0,1,…,6）との間の垂直距離（の二乗）がz=6の場合に最小であることによって発見的に説明することが可能である。より正確には、この（二乗）差は全てを物語る訳でない。それは、中央ビット位置（指数）（ゼロ又は１である。これが差をもたらす）より上のチャネル出力における（二乗）差のみならず、中央ビットに最も近い近傍ビットより上のチャネル出力における６つの（二乗）差も合計二乗ユークリッド距離に寄与するからである。例えば、z=6の場合、後者の６つの、より小さな寄与分それぞれは、図１の曲線上の第２の点と第３の点との間の（二乗）差に相当する。
【０００６】
反対の中央ビットを備えるクラスタ（チャネル入力のクラスタ）に相当するチャネル出力フィールド間の合計二乗（ユークリッド）距離は、相加性白色ガウス雑音（AWGN）を備えたチャネルを用いて中央ビットを区別することが可能な信頼性の尺度である（前述のクラスタは、中央ビットだけよりも多くの指数において異なり得る）。異なる雑音特性を備えたチャネルの場合、異なる距離尺度又は区別尺度を規定することが可能である。
【０００７】
特定のチャネル入力フィールドについて2次元光記憶の信頼度が低くならないようにするために、条件付符号化を用いて、図１中の曲線の最も右の点（すなわち、図２中の最も右のクラスタ・タイプ）を禁止することが考えられている。条件付き符号化は、(d;k)条件付き符号化が特別なケースである規則のより一般的な語である。例えば、１つのビットが1のビット６つによって取り囲まれているケースを禁止することが可能である。前述の制約の情報レート損失は許容可能なものである。しかし、その場合、最も近い６つの近傍ビットのうちの５つが１であり、中央ビットがゼロ又は１である場合に距離が最小になる。この状況の二乗ユークリッド距離は、前述の最小ユークリッド距離よりもわずかに大きいに過ぎない。これは、図１の曲線上の、最も右の点を除く点のうちで最も右の点（z=5、x=1）（図２中の、最も右のクラスタ・タイプを除くクラスタ・タイプのうちで最も右のクラスタ・タイプ）も禁止しなければならないことを意味する。ランダムな入力メッセージの場合、最も近い近傍が１であるzの生起の比は、二項係数
【０００８】
【数１】
2008502085.tif 000003
に比例する。その結果、z=5、z=1を禁止するコストは、z=6、x=1を禁止するコストの
【０００９】
【数２】
2008502085.tif 000004
倍である。このようにして、（局所）条件付き符号化によって、情報レートはかなり低下するが、平均信頼度のデータ依存性が基本的なやり方で解決される訳ではない。局所条件から逸脱する他の試行に関しては、禁止された特定の局所パターンが特定の低確率で生じることが可能になる弱条件付き符号も存在することが分かる。
【００１０】
図１の曲線上の点（すなわち、図２に示す別々のクラスタ・タイプのうちの単一クラスタ・タイプ）を禁止する前に、この曲線上の点が全て、通常のランダムな入力メッセージの場合に実際に生じることが分かる。前述の通常のランダムなメッセージの場合、最も近い６つの近傍ビットが１に等しいビットの比は低い（1/64）。より誤りがちなケースのこの比が小さいことによって、BERに対するその寄与度が軽減される。この比がもう小さくない（例えば、通常の比すなわち1/32の2倍よりも大きい）場合に問題が生じる。この観察によって、特定のz値でクラスタが生じる比に条件を課すことが示唆される。こうした比は、許容される如何なる入力メッセージ・フィールドについても実際にランダムなケースからあまり逸脱すべきでない。このことは、許容される入力メッセージ・フィールド全てにわたって最悪のBERのケースが、ランダムな入力メッセージにわたって平均化されたBERと実質的に同じになるうえで十分な条件である。前述の比を測定するうえで筋が通るストリーム・サイズは、例えば、誤り制御符号（誤り訂正符号、誤り検出符号）のストリーム・サイズであり、その復号器はビット検出器に従う。
【発明の開示】
【発明が解決しようとする課題】
【００１１】
本発明の目的は、前述の問題点がないようにし、記憶システムの最悪のケースのBER特性を改善し、信頼度を向上させ、特に2次元光記憶システム又は通信システムにおいて、特に、情報レートの大きな損失を伴わずにBERを確実に低下させる符号化装置及び符号化方法を提供することである。更に、対応する復号化装置及び復号化方法、並びに、コンピュータ上で前述の符号化方法及び／又は復号化方法を実施するコンピュータ・プログラムを提供するものとする。
【課題を解決するための手段】
【００１２】
この目的は、本発明によって、請求項１記載の符号化装置により、達成され、この符号化装置は、
ユーザ・データ・ストリームよりもシンボルが少なくとも１つ多い中間データ・ストリーム(i)にユーザ・データ・ストリームを変換する拡張装置と、
中間データ・ストリームを用いてスクランブル・ストリームのフィギュア・オブ・メリット値をスクランブル符号からスクランブル・ストリーム毎に反復的に判定する処理装置であって、スクランブル・ストリームは、中間データ・ストリームと同等に多くのシンボルを備えており、フィギュア・オブ・メリットはスクランブル・ストリームの一部分の収集体にわたる和であり、上記一部分が、スクランブル・ストリームからの少なくとも２つのシンボル位置を備え、和の各項が、中間ストリームの対応部分を用いた、スクランブル・ストリームの一部分のフィギュア・オブ・メリットであり、スクランブル・ストリームの上記一部分のそれぞれにおいて、シンボルの考えられる組み合わせそれぞれが、スクランブル符号からの、等しく多いスクランブル・ストリームにおいて生じる処理装置と、
上記メリット値から、最適なメリット値を選択し、フィギュア・オブ・メリットが最適メリット値に等しい最適なスクランブル・ストリームを選択する選択装置と、
中間データ・ストリームの対応シンボルに、最適なスクランブル・ストリームのシンボルをマッピングして、チャネルに出力するよう、チャネル・データ・ストリームを得る少なくとも１つのマッピング装置とを備える。
【００１３】
本発明は、符号化処理に局所無作為化装置を導入するという考えに基づいている。誘導スクランブルは、特定のオブジェクト関数（フィギュア・オブ・メリットとも呼ばれている）を最大にする一方で、記憶システムへの入力を無作為化する周知の手法である。電気通信システムでは、例えば、変調信号の、スペクトル特性が異常な（「先が尖りすぎている」）状態がないようにするためにスクランブル又は無作為化を備えるか、又は、（「先が尖った」スペクトルによる）干渉の影響を拡散させることが周知慣用である。光記録の分野では、前述のような誘導スクランブルは、K.A.Schouhamer  Imminkによる「Codes  for  Mass  Data  Storage  for  Mass  Data  Storage  Systems,  Shannon  Foundation,  Rotterdam,  1999,  chapter  13」に記載されている。しかし、実用に適用されてはいない。
【００１４】
本発明によれば、平均予測ビット誤りレートは、前述の１つのオブジェクト関数（フィギュア・オブ・メリット）として表すことが可能であり、このオブジェクト関数（平均）の線形性を利用する。何れの入力系列の場合にも、小容量スクランブル符号において、予測ビット誤りレートがランダムな入力データの場合と同様に良好なスクランブル符号語が存在していることが明らかになっている。本発明は同様に、（フィルタリング）通信システムの最悪のケースの平均パワーをそのランダムな平均以下（以上）にするよう適用することが可能である。
【００１５】
2次元光記憶と同様に2次元六角形格子上にビットが記憶される場合、本発明のスクランブル方法のコストは、施されるストリーム毎に６情報ビットである。よって、ストリームが長い場合、レート損失は小さいが、局所ではBERはなお大きいものであり得る。入力系列（2次元格子）毎に、６４個のスクランブル符号語のみの予測平均ビット誤りレート関数を求めればよい。本発明の方法はこの評価を効率的に行うことが可能である。
【００１６】
本発明による復号化装置は請求項１３に記載されており、この復号化装置は、
誤り訂正符号のチャネル符号語にチャネル・データ・ストリームを復号化するECC復号化装置と、
中間データ・ストリームにスクランブル符号語をマッピングすることによってチャネル符号語が生じるようにチャネル符号語から中間データ・ストリーム及びスクランブル符号語を見つける分離装置と、
ユーザ・データ・ストリームよりも少なくとも１つ多いシンボルを備える中間データ・ストリームにユーザ・データ・ストリームを拡張することによって中間データ・ストリームが生じるように中間データ・ストリームからユーザ・データ・ストリームを取り出すマッピング解除装置とを備える。
【００１７】
本発明は、請求項１記載の符号化方法によってユーザ・データ・ストリーム(m)が符号化されるチャネル・データ・ストリーム(r)を記憶する、請求項１５記載の記録担体にも関する。
【００１８】
対応する符号化手法及び復号化手法は請求項１２及び請求項１４に記載する。本発明の好ましい実施例は従属請求項に記載する。本発明の符号化方法によって符号化される信号は請求項１６に記載する。上記方法を実施するコンピュータ・プログラムは請求項１７に記載する。
【００１９】
好ましい実施例によれば、ヒストグラムを用いる。ヒストグラム手法の利点は、考えられるスクランブル符号語全てに対して中間ストリームをマッピングし、考えられるこれらの選択全てについてフィギュア・オブ・メリットを求める必要がないようにすることである。スクランブル符号Cにおいて合計|C|個のスクランブル符号語が存在しており、Kに等しい長さ（ブロック長）を符号語が有する場合、全ての可能性についてフィギュア・オブ・メリットを求めるうえでの合計計算量は、積（|C|K）に等しい。ヒストグラム手法は、ブロック長Kが大きい場合に計算量が更に削減されるという利点を有する。ヒストグラム手法は、中間系列を一度走査してヒストグラムを生成する。これは、K（すなわち、ブロック長）に等しい計算量を有する。ヒストグラムの操作の計算量は、集計のみが扱われるのでブロック長Kとは無関係であることが分かる。こうした集計の数値範囲は、Kの対数に比例するに過ぎない。ブロック長Kが非常に大きい場合、この計算量は、中間系列iを走査してヒストグラムを編集するうえでの前述の計算に対して無視することが可能である。
【００２０】
一般に、受信器は、メッセージを取り出す（「スクランブル解除する」）ために、特定のメッセージmに用いられたスクランブル符号語cの選択について通知されていなければならない。本発明によれば、この選択は、中間ストリームにメッセージを延長し、よって、冗長度の形式を付加する拡張装置によって伝えられる。この冗長度は、請求項１０記載のように、既知のシンボルがメッセージ・ストリームに連結される形式をとり得るか、又は請求項１１記載のように、誤り訂正符号化変換の形式をとり得る。
【００２１】
誤り訂正符号は固有に冗長である。中間ストリームの構成においてメッセージ・ストリームにこれら又はその他の形式の冗長度を付加することによって、符号化処理中に用いる、受信器によって検出される対象のスクランブル符号語の選択（不確実性）が許容される。例えば、請求項１０の場合、挿入された既知シンボルが存在する符号語内の位置（指数）において、スクランブル符号語のシンボル（例えば、バイト）を、前述の位置におけるシンボルの値から既知のシンボルをマップ解除する（例えば、請求項３記載のように減算する）ことによって取り出すことが可能である。
【００２２】
実用的なケースの多くでは、チャネル・データ・ストリームは、雑音、消去や他のチャネル誤りによって擾乱され得る。請求項１０記載の実施例が用いられるケースでは、既知のシンボルの位置における受信チャネル・データ・ストリーム（送出チャネル・データ・ストリームの、雑音のある複製）が、チャネル雑音が存在していることによって、誤って受信された場合、このことによって、スクランブル符号語の誤った選択の結論付けを受信器が行うことになる。よって、受信器は、受信チャネル・データ・ストリームをマップ解除（例えば、マッピング処理が、請求項３記載のように加算である場合には減算）することになり、スクランブル符号語のこの誤った選択（粗大復号化誤り）が生じることになり、これによって、一般に、復号化メッセージにおいてシンボル誤りが複数になり得る。よって、誤り伝播作用がこの場合、みられる。シンボル誤りの前述の爆発的増加がないようにするために、誤り制御符号化（誤り訂正符号化）によって保護されるやり方でスクランブル符号語の選択を受信器に伝えることが必要になる。一般に、チャネル誤りが存在している場合、中間シンボル・ストリームiの残りを誤り訂正符号によって保護することも必要である。別々の誤り訂正（制御）手法を用いてスクランブル符号語の選択を受信器に高信頼度で伝え、実際のペイロード（すなわち、既知のシンボル以外の、中間シンボル・ストリームの残り）を高信頼度で伝える場合、２つの誤り訂正符号器及び復号器が必要である。特に、スクランブル符号語の選択が小量の情報（例えば、1バイト、若しくは１つの１０ビット・シンボル、又はより少ないビット）であるため、別個の誤り訂正符号化が前述の小量の情報に施されることになる場合、これは、ブロック長がとても小さい誤り制御符号を必要とすることになる。
【００２３】
請求項１１記載の実施例の第１の利点は、スクランブル・コードから、ペイロード（メッセージ）と、スクランブル符号語の選択とを保護するために、２つの符号器（受信器において別個の復号器をそれぞれがやはり必要とする）ではなく単一の誤り制御符号器のみを必要とすることである。更に、この実施例を用いることによって、ブロック長がとても小さい誤り訂正符号を導入することがないようにもなる。ブロック長が小さな誤り訂正符号がチャネル誤りに対して設ける保護は固有に弱い（例えば、この小符号におけるビット（シンボル）が全て、チャネル誤りが理由で誤って受信される確率がある程度存在しているため）。この作用は、より大きな（チャネル）ストリーム内に特定の間隔距離を挿入することにより、又は、請求項１１記載の実施例を施すことになる場合に必要になる、ずっと大量の冗長ビット又は冗長シンボルを付加することにより、前述の符号のビットの拡散（インタリーブ）を行うことによって限定的な範囲でしか軽減することが可能でない。
【００２４】
更に、積分誤り訂正符号C’を用いることによって、a)C’からの受信符号語が存在する、スクランブル符号の考えられる|C’|/|C|コセットの選択によって伝えられる中間ストリームと、b)復号化されたC’の符号語と一致する、上記特定のコセットにおいて考えられる|C|の符号語の選択によって符号化中に用いられたスクランブル符号語とを受信器が取り出すことが可能になる。よって、合計受信情報量は、何れも高信頼度で取り出すことが可能な２つの部分を備える。
【発明を実施するための最良の形態】
【００２５】
本発明を次に、添付図面を参照しながら更に詳細に説明する。
【実施例】
【００２６】
図1及び図２は、前述の別々のHF信号レベル（図１）及び別々のクラスタ・タイプ（図２）を示す6角形格子上の2次元符号の概略的な信号パターンを示す。これらは、以下に更に詳細に説明する誘導スクランブル手法を施すことによってなくなることになる、本発明の背後にある課題を示す。
【００２７】
入力DIから出力DOまでのユーザ・データのサイクルは、インタリーブ１０、誤り制御符号（ECC）２０及び変調符号化３０、信号前処理４０、記録媒体５０上のデータ記憶、信号後処理６０、2値検出７０、並びに、変調符号の復号化８０及びインタリーブECC復号化９０を有し得る。ECC符号器２０は、種々の雑音源からの誤りに対する保護を設けるためにデータに冗長性を付加する。ECC符号化データは次いで、変調符号器３０に転送され、変調符号器３０は、データをチャネルに適合させる、すなわち、チャネル誤りによって損なわれる可能性がより低く、チャネル出力でより容易に検出される形式にデータを操作する。変調データは次いで、記録装置、例えば、空間光変調器や同様なものに入力され、記録媒体５０に記憶される。取り出される側では、読み取り装置（例えば、光検出器や電荷結合素子（CCD））は、疑似アナログ・データ値を戻し、この疑似アナログ・データ値は、もう一度ディジタル・データに変換しなければならない（2値変調手法の場合、画素毎1ビット）。この処理における第１の工程は、なお疑似アナログ領域において、記録処理においてもたらされた歪みを打ち消そうとする、等化と呼ばれる後処理工程６０である。次いで、疑似アナログ値のアレイが、ビット検出器７０を介して2値ディジタル・データのアレイに変換される。ディジタル・データのアレイは次いで、まず変調復号器８０（変調復号器は、変調符号化とは反対の処理を行う）に転送し、更にECC復号器９０に転送する。
【００２８】
例として、特定の2次元6角形符号を以下に示す。しかし、本発明の概括的な考え方、及び全ての方策は、一般に、如何なる2次元符号（好ましくは、2次元線形符号）にも適用することが可能であり、特に、如何なる2次元6角形格子符号又は2次元正方形格子符号にも適用することが可能であることが分かる。最後に、上記概括的な考え方は、符号の漸進的な変化が1次元であることによって特徴付けられる、（読み出しチャネルの回転対称性の有無にかかわらない）1次元符号又は複数次元符号にも適用することが可能である。
【００２９】
前述の通り、以下では、2次元6角形符号を考察する。2次元6角形格子上のビットは、ビット・クラスタによって識別することが可能である。6角形クラスタは、近傍格子位置にある、最も近い６つの近傍ビットによって取り囲まれた、中央格子位置にあるビットを有する。符号は1次元方向に沿って漸進的に変化する。2次元ストリップは、第１の方向に直交する第２の方向において互いに積み重ねられており、2次元符号が漸進的に変化することが可能なエンティティを形成するいくつかの1次元行を備える。ストリップ・ベースの2次元符号化を図４に示す。互いにコヒーレントに積み重ねられたいくつかのストリップは、幅広の2次元帯を形成し、これは、光ディスク上でらせん状に動かすことが可能である（前述の帯は、「幅広いらせん」とも呼ばれる）。幅広いらせん状の連続した回転間では、又は近傍の2次元帯間では、例えば、（ゼロ・ビット及びランド・マークによって埋めた）１つの（空）ビット行のガード・バンドを配置させることができる。
【００３０】
6角形格子上の2次元記録の信号レベルは、考えられる6角形クラスタ全ての完全な集合についてHF信号の増幅値のプロットによって識別される。更に、等方性の仮定（すなわち、チャネル・インパルス応答が円対称であるものとする）を用いる。上記仮定は、説明を簡単にすることを理由としており、本発明が適用可能になるうえで必須でない。このことは、７ビット・クラスタを特徴付けるために、中央ビットと、最も近い近傍ビットのうちの「１」のビット（又は「0」のビット）の数(６つの近傍のうちの0,1,…,6は「1」であり得る)とを識別するだけでよいことを示唆している。「0」のビットは、本願の表記ではランド・ビットである。通常の「信号パターン」を図１に示す。連続した幅広いらせん間に１つの（空）ビット行のガード・バンドを有する、11個の並列ビット行を備える幅広いらせんを前提とすれば、図１のケースは、（例えば、（波長が405nmの青色レーザ・ダイオードと、開口数がNA=0.85のレンズとを用いた）ブルーレイ・ディスク（BD）形式において用いるような）伝統的な1次元光記録と比較する1.7倍の密度増加に相当する。
【００３１】
前述の特許出願（欧州特許出願第02076665.5号（PHNL020368）明細書が2次元光記憶を一般的に示している一方、この文献に開示されているフィッシュボーン符号（変調符号である）の特定の実施例は、本発明によって適用されるものでない。本発明は好ましくは、指数Ｉの集合上の2元ベクトル全ての集合の線形（２を法とする）部分空間である符号（スクランブル符号と呼ぶ）を表す。
【００３２】
本発明によれば、誘導スクランブル手法を用いる。「ほとんど常に」又は「事実上常に」通常のランダムな出力系列を生成する無作為化装置は簡単である。系列はほとんど全て、通常の一様にランダムな系列の特性を有するので、何かを行う必要性はない。あるいは、単一のランダム・スクランブル系列（例えば、最大長シフト・レジスタ系列）を採用することが可能であり、入力系列を、法q=2としてスクランブル系列と加算することが可能である。前述のスクランブル・システムは周知である。前述のスクランブル・システムが記憶システム（2次元光記憶システムなど）に使用されたものとすれば、スクランブル器の入力系列（のかなりの部分）がスクランブル系列又はその2進補数に等しい、とても小さな確率が常に存在している。その場合、スクランブル器出力系列は、（部分的に）全てゼロ又は全て１になり、これは通常、ほとんどランダムである。その場合、前述の異常系列の読み出すうえでの信頼度は、前述の「全て１」の場合において許容可能な信頼度よりもずっと下であり得る。よって、前述の異常状況が存在していることは許容できない。記憶システムは、入力系列全てについてその信頼度要件を満たさなければならない。これは、「保証された」スクランブルを備えることを必要とする。
【００３３】
本発明によれば、スクランブル符号Cを用いることによって得ることが可能な特定の利点が活用される。Iを有限指数集合（例えば、ビットが記憶又は送信される、空間又は時間における点の集合）とする。このことの最も単純な例は、整数（指数）の系列である。このことのより高度な例は、6角形格子における、いくつかの（ビット）行である（ビット行のそれぞれは特定の長さに限定される）。
【００３４】
本願では、「ストリーム」の語を用いて、空間、時間（又は時空間）において点に関連付けることが可能な、Iのそれぞれの指数のシンボル値を表す。多くの適用例では、このストリームがシンボルの「ブロック」を備えるものと考えることが可能である。「符号語」という語を以下に用いる場合、前述の「ブロック」は実際には、「語」として呼ばれる。
【００３５】
本明細書ではビットの記憶又は送信を記載しているが、本願提案の方法は、3進シンボル又は更に高次のシンボルにも同様にうまく適用される。＋によって表す加算演算はシンボルのアルファベットに対して規定されるものとする。ビットの場合、これは、２を法とする加算になる。3進シンボルの場合、これは、３を法とする加算、又はガロア域若しくはリング等における加算であり得る。語は、Iによって指数化される位置全てにおけるそのシンボル値によって規定される。メッセージも、スクランブル・メッセージも語の例である。次に、y=(y1,y2,…,yd)をd個のビットの列とする。J=｛(j(1),j(2),…,j(d)｝を、指数集合Iの順序付けされた部分集合とする。i=1,2,…,dのときに、yi=zj(i)である場合に、yは語zと一致する。前述の部分集合Jは、ストリームの「一部分」又は（ブロック内の）ストリームの「シンボル部分」を規定する。最も通常の実用的な場合には、前述の部分は、特定の物理的な「近傍」に相当する。それぞれのサイズがdであり、語がzであるIの部分集合Jの収集体X、及び列y=(y1,y2,…,yd)の場合、fx(y|z)は、Jにおけるzとyが一致する、Xにおける集合Jの比として定義する。すなわち、fx(y|z)は、一部分の位置においてみられるシンボル列が特定の列yと一致する一部分の比を測定する。
【００３６】
次に、Cを語の集合とする。Cは、スクランブル符号として表す。シンボル位置（指数）の集合Jは、シンボル値の組み合わせ全てがJにおいて、Cからの同様に多くの語において生起する場合にのみ、平衡集合である。XをIのサイズdの平衡部分集合の収集体とする。語m毎に、かつ列y毎に、スクランブル号語c全てにわたってとられる、fx(y|c+m)の平均は1/qdである（ここで、q=2は、シンボルアルファベットQのサイズに等しい）。
【００３７】
よって、gを、Qdに対して規定される実値関数とし、Gを、G(z)=Σfx(y|z)g(y)として（浮動小数点）数に語をマッピングする関数とする。その場合、語m毎に、スクランブル符号Cからの語全てにわたるG(M+c)の平均は、長さdの列全てにわたるg(y)の平均に等しい。よって、G(m+c)がせいぜいこの平均であるようなスクランブル符号語が存在している。
【００３８】
前述の非常に一般的な観察を、以下の特別なケースに適用する。g(y)には、列ｙによって近傍が表されるビットの予測ビット誤りレート（BER）を採用する。Xには、シンボル位置全ての近傍の集合を採用する。スクランブル符号Cは、各シンボル位置の近傍がCの均衡集合であるようなものである場合、入力メッセージm毎に、m+cの予測BERがせいぜい、真にランダムな符号語の予測BERであるようにスクランブル符号語cを選択することが可能である。
【００３９】
ここで、本発明の背後にある主たる定理を述べることが可能である。近傍集合Nと、近傍yにおけるビット（シンボル）値の集合とを定め、中央位置i∈I毎に近傍i−Nがスクランブル符号語（スクランブル符号）Cの集合の平衡集合であるものとすれば、スクランブル符号c∈Cにわたるf(y|c+m)の平均は以下の式(定理)を満たす。
【００４０】
【数３】
2008502085.tif 000005
特に、全てゼロのストリームmの場合、
【００４１】
【数４】
2008502085.tif 000006
となる。これは、fx(y|z)の定義が、ｃのXにおける部分J全てにわたる和を引き起こすため、当然の結果となる。よって、c∈C全てにわたるfx(y|z)の和は、特定の列yに、Cからのスクランブル符号cの何れかにおける部分Jが一致する数を集計する2重和を|X|によって除算することを達成する。しかし、特定の部分Jについて、yに一致する、Cからのスクランブル符号語cの数は|C|q-dに等しい（部分JはCの平衡集合であるものとされるため）。次に、J全てにわたってこの結果|C|q-dを合計し、|X|によって除算することによって、全てゼロのストリームにmが等しい特別のケースについての上記定理が確認される。上記定理は、任意のストリームmについてあてはまる。
【００４２】
前の段落では、mが、考えられる何れかのストリームであり得る場合、考えられる和s=c+m全てを考慮に入れると、sの値全てが複数（すなわち、|C|）回生起することになる。よって、sの値から、その場合、c及びmの値を結論付けることは可能でない。よって、mを一意に復号化できることを可能にするためには、どのcを用いるかの選択を受信器に明らかにしなければならない。その結果、前の段落においてmと呼んだものの役割は、特に特許請求の範囲では、中間ストリームiとして表す。本発明によって提案している、ストリームmをストリームｉに延長することによって、ｓ’＝c+iが代わりに用いられる場合に、考えられるストリームs’全てがせいぜい一度しか生起しないことを確実にするある程度の冗長度が得られる。その場合、これによって、スクランブル（マッピング）されたストリームs’からc及びiの値を一意に取り出すことが可能になる。mからiへの拡張は、拡張装置の役割である。
【００４３】
誘導スクランブルを用いた符号化装置の概括的なレイアウトを示す構成図を図５に示す。この装置は、ユーザ・データ・ストリームmよりも少なくとも１つ多いシンボルを備える中間データ・ストリームiにユーザ・データ・ストリームmを変換する拡張装置１５０と、スクランブル符号Cの別々のスクランブル符号語cを受信中間データ・ストリームiにマッピングするいくつかのマッピング・エレメント１０１を備える第１のマッピング装置１００とを備える。出力（すなわち、マッピングされた別々のユーザ・データ・ストリームm’は、フィギュア・オブ・メリット（FoM）のメリット値を判定するいくつかの処理エレメント２０１を備える処理装置２００に入力される。こうしたメリット値vは選択装置３００に供給され、選択装置３００では、最適なメリット値voptが選択され、その使用によって、スクランブル符号語coptが選択される。第２のマッピング装置４００では、この最適スクランブル符号語coptを次いで元のユーザ・データ・ストリームmにマッピングして、最適にマッピングされたユーザ・データ・ストリームyを取得し、このユーザ・データ・ストリームyはチャネル・データ・ストリームとしてチャネルに出力される（例えば、記録担体５０上に記憶されるか、又は送信回線を介して送信される）。チャネル・データ・ストリームyとともに（、又はその中に組み入れられて）、最適スクランブル符号語coptについての情報も、復号器による利用のために送信される。
【００４４】
処理装置２００の処理エレメント２０１の実施例を例として図６に示す。処理エレメント２０１は、部分に制限するいくつかの並列制限エレメント２０２を備える。前述の制限エレメントは、例えば、特定のビットの、ある空間的又は時間的な近傍内で記憶又は送信されるいくつかの（一定数の）ビットを集める。一部分内のビット（シンボル）を整数内に集めることはハードウェア実施形態において特に魅力的である。それによって、一部分の考えられる値（すなわち、一部分内のシンボル値）全てのフィギュア・オブ・メリットを記憶するテーブルを備えるメモリ内のアドレスとして前述の整数を用いることが可能になるからである。最も一般的なケースでは、フィギュア・オブ・メリットは別々の部分について異なり得るものであり、よって、図６は複数のテーブルを示し、ここでは、例えば、部分0（例えば、シンボル・ストリームの最初）のフィギュア・オブ・メリットは、次の部分1（例えば、シンボル・ストリーム内で時間的に後続するか、又は空間的に先行する）のフィギュア・オブ・メリットとは別のものになる。部分全ての収集体はXとして表し、よって最後の部分は、0から番号を付した場合、|X|-1番目の部分である。
【００４５】
こうした制限エレメントの出力uは、テーブル・エレメントのアドレスとしてテーブル・エレメント２０３に供給される。こうしたアドレスは、一部分の値を備える。テーブル・エレメントは、前述の一部分の（局所）フィギュア・オブ・メリットを備える。こうしたテーブル・エレメント２０３の出力は全て、例えば、部分の（局所）フィギュア・オブ・メリットの、ストリーム毎の大局フィギュア・オブ・メリットへの加重平均化又は凸平均化を行う平均化装置２０４に供給される。請求項１に記載されたように、シンボル・ストリーム（例えば、シンボル・ブロック）のフィギュア・オブ・メリットは、部分毎のフィギュア・オブ・メリットの和である。適切な正規化によって、そうした和は、図６に示すように、平均になる。一般に、最適スクランブル符号語c_optの選択は、前述の一定の正規化因数による除算による影響を受けない（よって、この除算は重要でない）。本発明の効果全てをなお得ながら、部分毎（すなわち、局所）のフィギュア・オブ・メリット値の和又は平均をとることからいささかわずかな逸脱を考えることが可能であることが当業者には明らかである。以下に二乗を用いた例を記載する。ここでは、二乗演算がいわゆる凸(-cup)演算であるという特性を活用する。よって、加算、又は、同等には、平均化を記載している場合、下記凸平均化のケース、及び同様なものも入る。
【００４６】
本発明を次に、更に詳細に説明する。本発明によれば、上記式（定理）において平衡集合条件セットを満たす符号Cを施す。この条件は、位置i∈I毎に、近傍(i−N)がスクランブル符号Cの平衡集合（すなわち、符号語シンボル部分）であるべきであるという要件に相当する。
【００４７】
本発明の一次元の例は、以下に説明する。まず、指数集合Ｉ（全ての整数0,1,…,K−１の集合（ここで、K(K＞2)はストリーム長である））を考え、この指数集合上のビット集合（m0,m1,….mN-1）を考える。更に、(i−N)={i−1,1,i+1}（ここで、i=1,2,….,K−2）の形式のIの、順序付けされた部分集合J全て（すなわち、N={−1,0,1}）を考える。こうした順序付けされた部分集合J全ての収集体をXと呼ぶ。更に、整数、固定小数点数又は浮動小数点数に3ビット系列をマッピングするテーブルgが採用される（何れかのテーブルgを採用することが可能である）。具体的にするために、gは、3タップ・フィルタ出力の累乗（すなわち、二乗）として定義する。
【００４８】
g(a,b,c)=(0.1*a+0.7*b+0.2*c)2
前述のテーブルgの例は
【００４９】
【表１】
2008502085.tif 000007
であり得る。テーブル・エントリ数が大きくなると、あるいはgを計算することが可能であることは明らかである。特定のユーザ・データ・ストリーム（m0,m1,….mN-1)の場合、平均累乗Gは、Xにわたる、局所フィギュア・オブ・メリットgの平均として定義する。
【００５０】
【数５】
2008502085.tif 000008
m1及びmNが分からないので、平均累乗Gは、指数集合Iの端点（すなわち、n0及びnK−1)でのフィルタ出力ni
ni=0.1*mi−1+0.7*mi+0.2*mi+1
の累乗を有するものでない。
【００５１】
次に、スクランブル符号を定義する。第１の例として反復符号をCとする。すなわち、スクランブル符号語（K−2（３の倍数でなくてもよい）の長さのもの）全ては、
c=(c0,c1,c2,c0,c1,c2,c0,c1,c2,…,c0,c1,c2)
の形式のものである。その場合、３つのビット(c0,c1,c2)の組み合わせによってそれぞれが一意に規定される、合計23=8個のスクランブル符号語が存在している。Xにおける何れかの近傍（又は部分）J=(i−N)について、J=(i−N)に制限された符号語cがy=(ci-1,ci,ci+1)に等しく、yが(c0,c1,c2)の特定の順列であることが分かる。よって、Cにわたるgの平均を考えた場合、Jに制限された符号語全てにわたる局所フィギュア・オブ・メリットgの和は、長さ3の2進系列にわたるgの平均値（すなわち、0.385）に過ぎない。
【００５２】
【数６】
2008502085.tif 000009
ここで、符号語全ての、部分集合Kへの制限において、長さ３の考えられる2進系列全てはちょうど1度生起する（各Jは平衡集合である）。（この場合、部分系列は全て、2度生起することになり、同じ議論が続けられることになる、等。）ユーザ・データ・ビット・ストリームmをcに、２を法として加え（
【００５３】
【数７】
2008502085.tif 000010
で表す）、よってマッピング（又はスクランブル）されたストリームを得ると、
【００５４】
【数８】
2008502085.tif 000011
結果はなお、J=i−Nを備える指数における長さ3の2進系列全てにわたる和であるので、結果（この例では0.385）は変わるものでない。これが正しいのは、(mi-1,mi,mi+1)の加算（２を法とする）が反転可能演算であるからである。よって、既に述べたように、
【００５５】
【数９】
2008502085.tif 000012
となる。これは、ci及びmiをm’iに組み合わせるマッピング演算として、シンボルアルファベットに対する何れかの反転可能演算を採用することが可能であることを意味する。次に、スクランブル符号語c全てにわたる
【００５６】
【数１０】
2008502085.tif 000013
の平均を、XにおけるJ全てにわたる（すなわち、i(0＜i＜K−1)全てにわたる）、特定の部分集合j=i−Nに制限されたスクランブル符号語c全てにわたるgの平均
【００５７】
【数１１】
2008502085.tif 000014
の平均として求めることが可能である。定数値の平均も定数値であるので、スクランブル符号語c全てにわたる
【００５８】
【数１２】
2008502085.tif 000015
の平均も、前述の定数
【００５９】
【数１３】
2008502085.tif 000016
になる。ここで、
【００６０】
【数１４】
2008502085.tif 000017
がiに依存しないことを用いている。
【００６１】
【数１５】
2008502085.tif 000018
Cにわたる
【００６２】
【数１６】
2008502085.tif 000019
の平均が0.385であることは、
【００６３】
【数１７】
2008502085.tif 000020
が最大で0.385である符号語c_optがCにおいて少なくとも１つ存在している（すなわち、スクランブル（マッピング）されたユーザ・データ・シンボル・ストリームのG(フィルタ出力の平均累乗)が最大で0.385であるようなスクランブル符号語がなければならない）ことを示唆している。あるいは、スクランブル符号語のGが少なくとも0.385であるスクランブル符号語が少なくとも１つ存在していることが結論付けられたものであり得る。
【００６４】
関数gがJ毎に異なることが（すなわち、上記例「gi(,.,.,)」において）可能であり得ることが分かる。例えば、長さK（Kは偶数）のストリームを長さK/２の２つのサブストリームに分割することが可能である（第１のサブストリームにおいて第１の関数（テーブル）gAによって、かつ、第２の関数（テーブル）gBが施される第２のサブストリームによって）。その場合、長さKのストリーム全体にわたる、大局フィギュア・オブ・メリット関数Gの平均は、長さ３の2進系列全てにわたる、gAの（一様な）平均
【００６５】
【数１８】
2008502085.tif 000021
と、長さ３の2進系列にわたる、g2の（一様な）平均
【００６６】
【数１９】
2008502085.tif 000022
との、同様に重み付けされた(fifty-fifty)平均に等しい。
【００６７】
この例における符号Cの生成器行列は以下の通りである。
【００６８】
【数２０】
2008502085.tif 000023
近傍（一般にシンボル・パターンとも呼ばれる）に相当する３つの列にGが制限される場合、前述の３つの近傍列が何れも線形的に独立であることは明らかである。
【００６９】
更に、本発明の原理に影響を及ぼすことなくスクランブル符号の定義に非線形性を入れることが可能である（例えば、
【００７０】
【数２１】
2008502085.tif 000024
）。独立線形項「c1」をビット値の積「c0c2」に加えることによって、（c0,c1,c2）が、考えられる８つの組み合わせにわたって変えられる場合に、スクランブル符号語が近傍（シンボル・パターン）に制限されると、（この例では、３つの連続した指数のうち）考えられる８つの組み合わせ全てが確実にちょうど一回生起する（よって、全てが、同じ回数生起する）。
【００７１】
同様に、フィギュア・オブ・メリットGの線形性は、例えば、合計項数（この例ではK−2）に対して数がわずかであるか、又は、ここに記載する線形寄与分がGの特性を支配する程度に最大若しくは平均の全体振幅がGを歪める任意のいくつかの寄与分（例えば、シンボル部分に依存しない寄与分や、いくつかのシンボル部分のいくつかの寄与分の非線形的な組み合わせ等）を挿入することによって歪めることが可能である。本願提案の方法の利点は、例えば、線形平均Gが、加重平均によって、又は凸平均によって置き換えられた場合、なお残る。例えば、二乗演算は凸関数であり、
【００７２】
【数２２】
2008502085.tif 000025
に設定された場合、前述の凸性は、
【００７３】
【数２３】
2008502085.tif 000026
であることを示唆している。よって、関数Gは、元の値gの代わりにgの二乗値をテーブルに記憶させることが可能な線形上限を有しており、Gが通常のものよりも大きくない、マッピングされたユーザ・データ語をもたらすスクランブル符号語が存在していることは、本発明を上記上限（真のGの役割を果たし、本発明を適用することが可能である）に適用することによって当然もたらされる。
【００７４】
サイズが等しいことが必然でない何れかの数の部分にストリーム長Kを分割することが可能であり、本発明がなおあてはまることは明らかである。特別なケースとして、関数（テーブル）giは、指数i全てについて異なり得る。一様でない平均（すなわち、加重平均）を考えた場合に、重み付け関数を関数gに備え得ることも明らかである。
【００７５】
スクランブル符号の第２の例として、図７に示す線形帰還シフト・レジスタによって生成される、（長さK＞３の）考えられる系列全てをスクランブル符号語として考察する。シフト・レジスタの最初の3ビットの内容はシードと呼ばれている。(c0,c1,c2)と表す、（長さ３の）、考えられる23=8個の（2進）シード・ベクトルが存在している。図７に示すシフト・レジスタの出力系列は、帰納等式
(i+3=3,4,…,N−1)、
ci+3=(ci+ci+1+ci+2)  mod  2
として表すことが可能である。帰還シフト・レジスタの前述のシード(c0,c1,c2)が、長さ３の、考えられる2進系列全てにわたって変えられた場合、何れの部分J={i−1,i,i+1}においても、長さ３の、考えられる８つの2進列全てがちょうど1度生起する。よって、この場合にもJ={i−1,i,i+1}（i=1,2,…,K−2）それぞれが平衡集合であるので、反復スクランブル符号と同様な論拠が持続する。
【００７６】
何れのテーブルgを採用することも可能であることは明らかである。上記例の変形として、i:J={i−1,i+1}が入らないものとして近傍Nが定義される。その場合、上記例における符号語の数は、
c0+c1+c2  =0  mod  2、
例えば、
c1=c0+c2  mod  2
に設定することによって半分にすることが可能である。次に、位置{i−1,i+1}に対応する2ビット入力を有する関数（又は、より一般的にはgi）を考える。例えば、チャネル出力riが、チャネル入力ai（例えば、スクランブルされたユーザ・データ・ストリーム、すなわち、ai=m’i）とガウス雑音項「noisei」との和である相加性白色ガウス雑音チャネルLを考えることが可能である。
【００７７】
ri=ai+noisei
その場合、チャネル入力aiの平均二乗値と、平均二乗「noisei」値との比である信号対雑音比（SNR）はai-1及びai+1（すなわち、スクランブルされた特定のユーザ・データ・シンボルm’i-1及びm’i+1）によって変わってくる場合がある。チャネル出力riによってチャネル入力aiについて送信される期待量の情報（ビットの分数）が信号対雑音比（SNR）とともに対数関数的に増加することを表す周知のシャノン容量関数
Sh（SNR）=log（1+SNR（ｃi-1,ci+1））
を用いれば、対（ｃi-1,ci+1）毎に、かつ、結果として生じるSNR（チャネルの特性から分かっているものとする）に対して、結果として生じるシャノン容量Sh（ｃi-1,ci+1）を計算することが可能である。その場合、g(ci-1,ci+1)をSh(ci-1,ci+1)に等しく設定することが可能であり、上記論拠を適用して、G（すなわち、X（N={-1,1}における近傍(i−N)全てにわたるSh（,.,）の平均）が、スクランブル符号語全てにわたる、Gの一様な平均に等しい、長さ２の系列全てにわたる、gのその一様の平均値以上であることを示すことが可能である。よって、最小有効ビット数がストリーム毎に（平均で、期待ベースで）送信されることを保証することが可能である。この場合にも、局所フィギュア・オブ・メリットgが格子I内の指数iに依存することを可能にし得ることが分かる。
【００７８】
上記例における第iの送信（又は記憶）の信号対雑音比（SNR）が、第iの近傍{i−1,i+1}に入らないci-２にも依存する場合、近傍{i−1,i+1}に入っていないシンボル値ci-2にわたって、信号対雑音比を（近傍（ci-1,ci+1）に入るシンボル値対の特定値について）最小にすることが可能である。この最小化の結果を次いで、局所フィギュア・オブ・メリットg(ci-1,ci+1)として用いる。前述のケースでは、G及びgについての前述のような論拠によって、達成可能な最悪のケースの平均シャノン容量を保証することが可能になる。このケースは、スクランブル符号語の数│C│とともに増加する符号化計算量と、部分集合Jのサイズが増えるにつれて、元の近傍Jに入っていない更なるシンボルの影響下で、保証された最悪のケースの平均結果を最小にしなくてよいこととの間のトレードオフも示す。例えば、(c0,c1,c2)にあてはまる単一パリティ・チェック等式をもう前提にすることが可能でないため、符号語の数を2倍にする（８にする）J=(i−N)（N={−2,−1,1}）を用いることが可能である。
【００７９】
本発明の主たる対象である誘導スクランブル手法と、誤り制御符号化との組み合わせを例証するために、以下のことを考察する。前述の8個のスクランブル符号語を備えた反復符号は、全て１のベクトルのガロア域GF(23)にわたる、倍数の集合とみなすことが可能である。ここでは、「全て１」の「１」は、GF（２３）の要素ともみなすものとする。全て１のベクトルが符号語である、GF(23)にわたる誤り訂正符号が存在する。ここでの「ベクトル」の語によって、指数集合Iが2次元以上の場合を排除しないものとする（その場合、誤り制御符号化の分野内では非慣習的であるが、「アレイ」のほうが適切になる）。
【００８０】
シンボル間干渉を備えた相加性白色ガウス雑音チャネルの場合、i(i’≠i)である他の位置での出力ri’は、指数iでの入力aiについての情報も明らかにし得る。
【００８１】
チャネル出力のサンプリング・グリッドは、チャネル入力位置の集合に一致しなくてよい。例えば、存在しているチャネル入力シンボルよりも多くのチャネル出力サンプルが存在しているようにチャネル出力をオーバーサンプリングすることができる。
【００８２】
チャネル出力が2進の場合、シャノン容量は単に、エントロピー項の組み合わせである。例えば、入力が0及び１に等しく分布している場合、シャノン容量は1−h(ｐE)に等しい（ここで、pEはシンボル（すなわち、ビット）誤り確率であり、h(.)は2進エントロピー関数h(x)=−xlog2(x)−(1−x)log2(1−x)である。シンボル誤り確率pEはI内の点iの特定の近傍i−Nによって変わってくる場合がある。その場合、本発明の条件を満たすスクランブル符号の場合、当然、誤り確率の、シンボル単位の平均エントロピーが、近傍J=(i−N)にわたる、ｈ（pE）の、平均ほど悪くない（平均を上回る）スクランブル符号語c_optが常に存在していることになる。指数iに対する依存度の場合、X内のJ全てにわたって更に平均化することが必要である。
【００８３】
本発明の最も単純な実施例の１つとしては、局所フィギュア・オブ・メリットgとして、シンボル誤り確率（「レート」）PE自体を、特定の近傍J=(i−N)の関数とみなすことが可能である。上記近傍への依存は、線形であっても非線形であってもよい、チャネル内に生起するシンボル間干渉によって生じる。スクランブル符号Cが本発明の条件を満たしている場合、スクランブルされた特定のユーザ・データ・シンボル・ストリームが、特定のJ内の部分系列全てにわたる、シンボル単位の誤り確率の一様な平均よりも悪くないようなスクランブル符号語c_optが確実に存在している。やはり、J（例えば、Jがi−Nの形式のものである場合におけるi）への依存の場合、X内のJ全てにわたって更に平均化する必要がある。前述の実施例では、2進エントロピー関数h(.)は、この実施例と比較すれば、より大きなｐEの寄与分に対して、より小さなｐEの寄与分を増幅する。
【００８４】
反復符号がスクランブル符号として用いられる場合（これは、符号が単純であることによって効果的である）、「カラーイング(coloring)」を用いて符号を構成することが可能である。その場合、Iの特定の部分集合Jに備えられる指数全てが別個のカラーを確かに有していなければならない。
【００８５】
反復符号を備えた1次元の例の場合、カラーイングは、
(0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,….)
である。この例ではX内の何れのJも3つの別々のカラーを有している。
【００８６】
6角形格子に用いるよう企図される対象の反復スクランブル符号の場合、実施例を次に示す。７つの要素の6角形クラスタを併せて構成する、中央点と、その６つの近傍とを考えれば、クラスタ（ユーザ・シンボル部分とも呼ばれる）の７つの要素（シンボル又はビット）のそれぞれには、別々のカラーが与えられる（７つの要素のそれぞれに別々のラベルを割り当てることに同等である）。６角形平面を、前述の集合によってタイリング（すなわち、タイルに分割）することが可能であることを検証できる。その第１の実施例を以下の表に示す。
【００８７】
【表２】
2008502085.tif 000027
別々のカラーそれぞれは、このテーブル（多くの変形が存在する）における別々の番号（ラベル）によって表される。カラーイングのこの特定の実施例では、カラー番号は、2行下がった場合（７を法として）２ずつ増加する。真の6角形格子と違って、最も近い近傍への垂直距離及び水平距離は、この表では、等しくないことが分かる。
【００８８】
スクランブル符号語c_optを見つける直接的なやり方は、スクランブル符号語全て（の部分集合）についてストリーム毎のフィギュア・オブ・メリット関数Gを求めることである。その場合、計算量は、スクランブル符号語の数│C│とストリーム長Kとの積に比例する。
【００８９】
c_optを見つける代替的なやり方は、いくつかのヒストグラム（カラー毎に一ヒストグラム）を以下のように用いることである。その場合、ヒストグラムの集計の計算量は、ストリーム長に比例する。ストリーム長が大きい（例えば、約数千ビットである）ものとすれば、残りの計算量は一般に無視できる。よって、計算量は、約│C│（スクランブル符号語の数）の係数、削減される。
【００９０】
いくつかのヒストグラムを用いた符号器の概括的なレイアウトを図８に示す。特定の部分（特に、選択装置３００（最適なメリット値voptを選択し、最適なスクランブル符号語coptを生成（又は選択）する（ここでは、別個の生成器３０１を備える））、及び最適なスクランブル符号語coptをユーザ・データ・ストリームmにマッピングする第２のマッピング装置４００）は図５に示すものと同様であるか、又は同一である一方、符号器の第１の部分は異なっている。
【００９１】
上記符号器は、以下に説明する、いくつかのヒストグラムHを計算する1つ又は複数の集計エレメントを有する集計装置５００を備える。こうしたヒストグラムHは、いくつかのヒストグラム変換エレメント６０１を有するヒストグラム変換装置６００に供給される。ここでは、スクランブル符号語は全て異なるので、スクランブル符号語cの、考えられる選択それぞれによって、ヒストグラムそれぞれの別々の変換が達成される。よって、スクランブル符号語の数（すなわち、図においてn=│C│によって示される│C│）と同数の、ヒストグラムの集合の変換が存在している。あとで、このことは、３つの2進シンボル（ビット）を備える部分について1次元の場合の例によって示す。
【００９２】
集計装置５００の実施例を更に詳細に図９に示す。この集計装置は、部分に制限するいくつかの並列制限エレメント５０１を備える。こうした制限エレメント５０１の出力uは、部分の値の生起の頻度を集計する1つ又は複数の集計エレメント５０２に供給される。こうした集計エレメント５０２の出力はヒストグラムHである。
【００９３】
例えば、1次元ビット・ストリームからの３つの後続ビットを一部分が備える例では、一部分の、考えられる内容は23=8個（すなわち、列000,001,010,,,,,111）存在している。こうした列は、整数0、1乃至7によって識別することが可能である。一般に、別々の部分が重なり得る（すなわち、共通のシンボル位置を有し得る）。部分X全ての収集体は、部分集合内の部分が重ならないように、いくつかの（この例では、３つの）部分集合に分割することが可能である。例えば、部分の収集体Xの第１の部分集合は、{i−1,i（３の倍数である）,i+1}の形式の指数を備えた部分全てを備える。収集体Xの第２の部分集合は、iが、３の倍数に１を加えた数である、上記形式の部分全てを備える。上記収集体の第３の部分集合は、iが、３の倍数に２を加えた数である部分全てを備える。一般的なケースについて述べたように、同じ部分集合内の別々の部分が、共通の指数を何ら有していない（すなわち、共通のシンボルを何ら有していない）ことは明らかである。このことは、図９によって示す。すなわち、部分の収集体Xの部分集合毎に、ヒストグラムは、部分内の考えられるシンボル列の生起の頻度を表す。前述の方法は、1次元の場合に用いるだけでなく、例えば、あとで説明する６角形格子の場合にも用いることが可能である。その場合、部分全ての収集体の別々の部分集合はA=7個存在している（単一の部分集合内の部分には重なりはなく、（2次元）反復符号語の選択によって一意に変換される）。
【００９４】
次に、図８では、A=3であり、３つのヒストグラムが作成される。第１のヒストグラムは、考えられる8つの値（000,001,…,111）のそれぞれが収集体の第１の部分集合において生起する頻度を集計する。第２（第３）のヒストグラムは、収集体Xの第２（第３）の部分集合の同様な集計を表す。更に、反復符号を用いるものとする。反復符号ほど単純な符号を用いることによって、当然、収集体の第１の部分集合、第２の部分集合及び第３の部分集合からの3つのタイプの部分のそれぞれが、反復符号からの特定のスクランブル符号語の選択によって一意に（すなわち、部分集合毎に一意に）影響を受けることになる。収集体の部分集合毎に、スクランブル符号語の各選択は、その部分集合における部分の値の別々の変換を示唆している。図８に示すように、スクランブル符号語の数（すなわち、n=│C│）と同数の、A（この例では３）個のヒストグラムの集合を処理する変換装置が存在している。よって、合計で、A│C│個（この例では、3│C│個）の個々のヒストグラムが変換される。収集体の部分集合毎の変換ヒストグラムは、収集体全体にわたって、合成ヒストグラムに合計されるものである。よって、変換されたヒストグラム集合によって、中間シンボル・ストリームと、特定のスクランブル符号語との互いのマッピングである、シンボル系列における部分(000,001,…,111)の生起の頻度を計算するうえで十分な情報が得られる。これは、部分のフィギュア・オブ・メリット（例えば、図６のような表によって実施される）が、テーブル全てについて同じテーブル値を有する（すなわち、フィギュア・オブ・メリットは、時間的にも空間的にも変動するものでない）ことを前提としている。ヒストグラム（集計）の定義も、部分毎フィギュア・オブ・メリットによる全体フィギュア・オブ・メリットの定義も、加算（「和」）に基づくことを共通としていることが分かる。よって、部分毎局所フィギュア・オブ・メリットの和は、考えられる部分(000,001,…,111)全てのフィギュア・オブ・メリットが分かっており、マッピングされたシンボル・ストリームにおいて、こうした部分値のそれぞれが生起する頻度が、３つの変換ヒストグラムの和によって表されるようなものである場合に、計算することが可能である。次に、フィギュア・オブ・メリットを、スクランブル符号語の考えられる選択（n=│C│個の選択）毎に計算することが可能であり、最適符号語c_optを、中間シンボル・ストリームiとの最終マッピング（例えば、ビット・ストリームの場合、2を法とする加算）に選択し、用いることが可能である。
【００９５】
図５の方法は（|C|K）の計算量を有しており、図８の方法の計算量はたったKである。例えば、6角形格子について表した例のような、|C|が27＝128である、スクランブル符号のサイズの場合、このことによって、顕著な効果がもたらされる。
【００９６】
上記では、それぞれのサイズがdであり、語がzである、Iの部分集合Jの収集体X、及びy=(y1,y2,…,yd)である列の場合、fx(y│z)は、Jにおけるzとyが一致する、Xにおける集合Jの比として定義されている。Jが、(i−N)の形式のもの（すなわち、中央指数iにシフトされた特定の近傍Nのバージョン）であるものとする。次に、カラーlの場合、fx(y│z,l)を、Jにおけるzとyが一致する、Xにおける集合J=i−Nの比とする（iはカラーlを有する）。カラーl全てにわたってfx(y│z,l)を合計した場合、fx(y│z)が得られることが分かる。
【００９７】
【数２４】
2008502085.tif 000028
を求める場合（すなわち、全て0の符号語0の場合）、ヒストグラムfx(y│m,l)の集合が分かっていることで十分である。それは、fx(y│m,l)が分かっていることは、fx(y│m)が分かっていることを示唆しているからである。その場合、G(m)=Σfx(y│m)g(y)は、y個のベクトルの数（すなわち、qd）に比例した作業量によって計算することが可能である。
【００９８】
シフト不変近傍概念（すなわち、J=i−N）によって、中央指数iがカラーlを有していることが分かっている場合、Jにおける（他の）指数のカラーも分かっていることが分かる。
【００９９】
【数２５】
2008502085.tif 000029
（ここで、c0=1、c1=0、c2=0である）を求めるものとし、カラーlが、スクランブル符号語cl（「c  sub  l」）におけるビット値に相当するものとする。その場合、中央カラーl=0を有するヒストグラムの場合、その中央指数でのメッセージ・ビットにc0=1が加算されることによって中央ビットが反転させられることが分かっている。この加算は、ヒストグラム
【０１００】
【数２６】
2008502085.tif 000030
を変換する（ここで、y’及びyは、中央ビットに相当するビット値において異なる）。
【０１０１】
次に、中央カラーl=1を有するヒストグラムの場合、中央ビットの左のビットが、その左の近傍でのメッセージ・ビットにc0=1が加算されることによって反転させられることが分かっている。この加算は、ヒストグラム
【０１０２】
【数２７】
2008502085.tif 000031
を変換する（ここで、y’’及びyは、中央ビットの左のビットに相当する(すなわち、指数i’=i−1（ここで、iは中央指数である）での)ビット値において異なる）。
【０１０３】
次に、中央カラーl=2を有するヒストグラムの場合、中央ビットの右のビットが、その右の近傍でのメッセージ・ビットにc0=1が加算されることによって反転させられることが分かっている。この加算は、ヒストグラム
【０１０４】
【数２８】
2008502085.tif 000032
を変換する（ここで、y’’及びyは、中央ビットの右のビットに相当する(すなわち、指数i’=i+1（ここで、iは中央指数である）での)ビット値において異なる）。
【０１０５】
このようにして、特定のスクランブル符号語について、ヒストグラム全てfx(.│m,l)を、
【０１０６】
【数２９】
2008502085.tif 000033
の順列によって計算することが可能である。前述の符号語例のみならず、何れのスクランブル符号語cにもこのことがあてはまることは明らかである。次いで、
【０１０７】
【数３０】
2008502085.tif 000034
を、yベクトルの数（すなわち、qd）に比例する作業量によって計算することが可能である。スクランブル符号語毎に、ヒストグラムを並べ替えるための合計作業量は（高々）、カラーの数と、yベクトルの数（すなわち、qd）との積に比例する。この積がストリーム長Kよりも小さい場合、この手法によって、
【０１０８】
【数３１】
2008502085.tif 000035
を直接求めることに対して計算資源が節減される。
【０１０９】
図１０は、別々のカラー（又はラベル）が、上記テーブルによってチャネル・シンボルに割り当てられる、6角形格子上のチャネル・データ・ストリームの一部を示す。クロスハッチングは第１のシンボル値（例えば、ビット値「1」）を表し、ハッチングがないことはチャネル・シンボルの第２のシンボル値（例えば、ビット値「0」）を表す。
【０１１０】
前述のタイリングによって、7個の集合上で元々規定されたカラーイングが６角形格子全体に拡張される。集合（タイル）内では、単一のパリティ・チェック符号（すなわち、6つの情報ビット及び１つのパリティ・ビット）が好ましくは規定される。カラーイングを用いれば、この符号が全てのタイルについて繰り返され、よって、26=64個の符号語を備える長い反復符号が作成される。単一パリティ・チェック等式を用いることによって、符号語（（特定のメッセージmについての）そのフィギュア・オブ・メリットを求めるものとする）の最大数が27から26に削減されており、よって、符号化の計算量が削減される。前述の削減は、特定の入力位置iでの局所フィギュア・オブ・メリット関数(g)が、位置i自体でのチャネル入力に実質的に依存している訳でなく、位置（i−N）（差分近傍指数Nの集合はゼロ・ベクトルを有するものでない）でのその近傍にのみ依存している場合にのみ好ましい。この反復符号の場合、任意の近傍（i−N）が別々のカラーのちょうど６つのビットを有しており、よって、情報集合（すなわち、シンボル部分）であることが分かる。これによって、2次元符号の例の場合の、上記定理のための符号の構成を終える。
【０１１１】
以下の段落では、計算に対する同様なヒストグラム・ベースの手法のより一般的な処理を表す。
【０１１２】
以下では、Iにわたる総和を一回必要とし（前処理工程）、c毎にヒストグラムを操作する、f(y│m+c)を求める代替的な方法を説明する。スクランブル符号が、前述のタイリングに基づいた格子カラーイングを用いて構成されているものとする。カラー（ラベル）の集合はUによって表す。チャネルの入力及び出力の格子の指数集合Iを次いで、互いに素な部分集合Iu（u∈U）に分割することが可能である。u∈U毎に、経験的な比fu(y│s)（s=m+c）は、
fu(y│s)=1/n│{i∈Iu│j∈N全てについて、yj=si-j}
によって定義され、ここで、nはIのサイズである。先行して定義された経験的な比は、カラー全てにわたる単純和による新たな、経験的な比から計算することが可能である。
【０１１３】
f(y│s)=Σu∈Ufu（y│ｓ）
スクランブル符号は、何れのスクランブル符号語の場合も、等しいカラー（すなわち、等しいラベル）の格子点が同じ符号語シンボル値を呈するという特性を有している。次に、j∈Nの場合、等しいカラー（ラベル）を{i-j/i∈Iu}からの点全てが有しているということを、近傍集合j∈N内の一定の指数について、タイリングの定義が示唆している。カラーが等しい点上でCが一定であるので、i∈Iu毎に
ci-Δj=zj（u,c）
があてはまるようなシンボル値zj(u,c)が存在している。
【０１１４】
よって、
fu(y│m+c)=1/n│{i∈Iu│j∈N全てについて、mi-j=yj−zj（u,c）}│
があてはまる。
【０１１５】
よって、z(u,c)によって(z1(u,c),z2(u,c),…,zn(u,c))と表される場合、
fu(y│m+c)=fu（y−z(u,c)│m）
があてはまる。
【０１１６】
この式は、以下のように用いることが可能である。まず、スクランブルするものとするメッセージmを前提とすれば、カラーu全て及び長さaのq元ベクトル全てについて、fu(y/m)は計算される。このことには、格子点全てにわたる総和が関係する。後に、カラーu毎に、かつ符号c∈C毎に、fu(y│m+c)が、上記式を用いて計算される。zj(u,c)のj番目のエントリが、何れのi∈Iuについても位置i-Δjにおけるcの値に等しいことが分かる。
【０１１７】
反復構成を用いるので、GF(27)にわたる誤り訂正符号が用いられた場合、別々のカラーを備えたビットを一シンボル内に集めると、上記提案されたスクランブル符号は、全て１の符号語と、GF（27)からの任意の係数との積を備えることになる。GF（214）の場合、２つのタイルをシンボルにグループ化することが可能である。７及びその倍数がシンボル寸法として望まれない場合、上記テーブルにおいて表すカラーイングの構成は、単一行上での反復（例えば、0,1,,,7からの数、及びGF（28）の使用）によって拡張することが可能である。
【０１１８】
以下には、8ビットのバイトを処理する誤り制御符号と、上記提案された誘導スクランブル手法とを組み合わせると、より好ましい特性を有する8個のカラーイングを示す。
【０１１９】
【表３】
2008502085.tif 000036
6角形格子のこの８個のカラーイングは、誤り制御符号化との組み合わせに適した、より好ましい特性（以下に説明する）を有する。スクランブル符号語長の選択に関しては、筋が最も通る選択は、光記憶チャネルに後続して復号化される第１の誤り訂正符号のストリーム・サイズと（ほぼ）重ならせることである。その場合、上記提案された誘導スクランブル手法によって、「真に」（すなわち、一様に）ランダムな入力データの「通常の」期待値にそのストリーム内の予測ビット誤り数が制限される。
【０１２０】
別々のスクランブル符号語の、ユーザ・データ・ストリームへのマッピングは、図１１（2次元の場合）及び図１２（1次元の場合）に示す。図１１には、ユーザ・データの2次元ストリップSの一部（図１０に示すように既にラベルが付けられている）を示す。この例では、中央シンボルb0と、この中央シンボルb0を取り囲む、最も近い６つの近傍シンボルb1乃至b6とを備えるユーザ・シンボル部分をUによって示す。左側には、別々のスクランブル符号語cの別々の符号語シンボル部分cu0乃至cuN-1を表す（ここでは、ラベリングされたユーザ・データにマッピングされている）。スクランブル符号語cは、いくつかの同一の符号語シンボル部分cuを備え、各符号語シンボル部分は一定数の符号語シンボルを有する。マッピングを更に詳細に説明するために、例えば、中央ビットb0には第１のラベルl0が付され、周囲ビットb1乃至b6にはラベルl1乃至l6が付されているものとする。
【０１２１】
マッピング工程の第１の反復では、第１の符号語シンボル部分c0をストリップSのユーザ・シンボル部分U全てにマッピングする。よって、例えば、第１の符号語シンボル部分cu0の第１の符号語シンボルcu00(=0)が、ストリップSに存在しているラベルl0全てにわたってマッピングされる。その後、各反復において、フィギュア・オブ・メリット（FoM）のメリット値が判定される。第１の反復では、ビット列「0000000」が、よって、ユーザ・シンボル部分U全てに割り当てられる。
【０１２２】
更なる反復では、他の符号語シンボル部分cu1乃至cuN−1がユーザ・データ・ストリームに同様にマッピングされる（例えば、第２の反復では、第１の符号語シンボルcu10(−1)がラベルl0等全てにわたってマッピングされるので、ビット列「0000001」が、ユーザ・シンボル部分U全てに割り当てられる。）
各反復では、マッピングされたシンボル符号語部分の符号語シンボルが次いで、背後にあるユーザ・シンボル値に加算（2進の場合、２を法として加算。M進の場合、Mを法として加算）される。その後、各反復では、フィギュア・オブ・メリット（FoM）のメリット値を判定する。
【０１２３】
図１２では、1次元ユーザ・データ・ストリームの部分（各ユーザ・シンボル部分が５個の後続シンボルを有する）を示す。図１１に示す2次元のケースについて説明したように、別々のスクランブル符号語cの別々の符号語シンボル部分cu0乃至cuN-1は、5個の別々のラベルl0乃至l4によって、先行してラベリングされているユーザ・データ・ストリームのユーザ・シンボル部分Uにマッピングされる。BERは、ビット検出の後にしか分かるものでない（符号器内では分かるものでない）。よって、「BER」の語を用いる場合、特定のチャネル・モデルを用いたBERの予測を意味する。格子指数集合Iにおける位置ｉでのビット誤り事象の前述の予測は、近傍位置（i−N=｛i−n|n∈N｝）によって変わってくる。位置iでのビット誤り確率の計算では、i−Nの外側の位置のシンボル値は任意（例えば、全てゼロ）に選んでよく、モデルに備えられていないビット位置にわたる、この予測BERの「最悪のケース」を見つけるよう、考えられるいくつかの組み合わせにわたって変えてもよい。
【０１２４】
誘導スクランブル器の役目は、「好適な」スクランブル符号語ｃ＊
ｃ＊=arg  minc∈CBER(m+c)
を見つけることである。
【０１２５】
入力アレイ（「メッセージ」又は「ユーザ・データ・ストリーム」）にスクランブル符号語ｃ＊を加算することは符号化処理とみなし得るので、誘導スクランブル器は符号器である。完全にするために、誘導スクランブル器の入力データは実際には他の符号化処理の出力であり得ることが分かる。更に、一般化するために、対象とする必要がある符号語の数は、部分集合S⊂Cに削減することが可能であることが分かる。
【０１２６】
【数３２】
2008502085.tif 000037
ここで、
【０１２７】
【数３３】
2008502085.tif 000038
である。
【０１２８】
よって、
【０１２９】
【数３４】
2008502085.tif 000039
であるような符号語c’∈Sが存在する。
【０１３０】
言葉では、部分集合Sにわたる、BER(c+m)の最小値のみ（スクランブル符号Cの一部（α＜１）を有する）をサーチした場合、このコストは高々、保証された予測ビット誤りレートの増加（１/α）であることが分かる。よって、mが変更されない（すなわち、全てゼロの語のみを有する部分集合Sにサーチを限定する）場合、BERは最大でも、符号全体にわたる平均BERの一部（1/α=64）である。
【０１３１】
前述の通り、誘導スクランブル・サーチの単純な実施形態は、考えられるスクランブル符号語c全てについてBER（m+c）を求め、BER(m+c*)が最小の符号語c*を選ぶものである。候補スクランブル符号語cのBER（m+c）を単純に求めることは、y全てについてf(y/m+c)を求めることを必然的に伴う。候補スクランブル符号語c毎に、格子指数集合I全体にわたる総和が関係する（これは、符号語長Kに等しいサイズを有する）。
【０１３２】
Cからの符号語の品質が検査される順序が重要でないことは明らかである。直近での対象の符号語dからのベクトルz(u,d)から、対象の符号語cからのベクトルz(u,c)を得るのが比較的単純であるようなやり方（グレイ・コ―ドのようなやり方）でCからの語を順序付けることによって、このことによる便益を受け得る。
【０１３３】
前述の通り、適切な符号化代替策を、考えられる情報列毎に選択することによって、最悪のケースのBERが、平均のケースのBERを超えないようにすることが可能である。以下では、このことを誤り訂正符号と組み合わせる方法を説明する。
【０１３４】
この問題が分かるために、メッセージ列mが誤り訂正符号Dからの語ｄ(m)に符号化されるものとする。語d(m)には、スクランブル符号Cからの適切な語（例えば、c(d(m))が付加されるので、最終的には、語d(m)+c(d(m))がチャネルに出力される（例えば、媒体上に書き込まれる）ことになる。よって、Mが、符号化することが可能な、考えられる列全ての集合を表す場合、記録することが可能な語の集合は、
X=｛d(m)+c(d(m)|m∈M｝
に等しい。
【０１３５】
この問題点は、Xの誤り制御能力がDの誤り制御能力よりもかなり悪い場合がある点である。
【０１３６】
高累乗（powerful）線形誤り符号EにC及びDが備えられていること、及び、語が全てゼロであることのみがC及びDに共通であることを確実にすることによって、集合Xが、好適な誤り制御能力を有していることが確実になる。この場合ではXがEに備えられているので、d(m)+c(d(m))を取り出すために、Eのどの復号化アルゴリズムも用いることが可能であり、これから、ｍを取り出すことが可能である。ある程度明確な例を、2次元符号のケースについて表す。この例は実際に、米国特許第5,671,236号明細書及び米国特許第5,845,810号明細書記載のいわゆるラムダ・トリックを用いた、スクランブル符号及び誤り訂正の組み合わせを表す。
【０１３７】
Eを[n  k]符号とする。ここで、シンボルは8ビットのバイトである。すなわち、Ｅからの語は、nバイトを備えるか、又は、換言すれば、8nビットを備える。Eは、１のみを備える語を有しているものとする。その場合、線形性によって、バイトx毎に、Eは、xの、n倍の反復を備える語を有している。
【０１３８】
符号C⊂Eは、６４語（それぞれはnバイトを備える）を有している。これは以下のように説明する。等しいカラーのビットは同じ値を有しており、ビットが「１」に設定される、｛0,1,2,3｝からのカラーの数も、ビットが「１」に設定される、｛4,5,6,7｝からのカラーの数も偶数である。すなわち、Cは、形式(x,x,…,x)の語全てを有している。ここで、x0+x1+x2+x3≡0(mod2)であり、x4+x5+x6+x7≡0(mod2)
であるようなx=（x0,x1,…,x7）である。
【０１３９】
次に、上記テーブルの8個のカラーを備えた6角形格子のカラーイングを考える。i=0,1,…,7の場合、カラーiによってカラーイングされた点の近傍のカラーは以下の通りである（ここで、カラー指数は、８を法として読むものとする）。
i+2            i+3
i+7            (i)            i+1
i+5            i+6
各近傍の6個の点は別個のカラーによってカラーイングされることが分かる。iによってカラーイングされた点の近傍にある、欠けている２つのカラーは、i及びi+4である。よって、何れの近傍からの6個の点も、｛0,1,2,3｝からの３つのカラー及び｛4,5,6,7｝からの３つのカラーによってカラーイングされる。この観察と、Cの定義とを組み合わせれば、何れの近傍においても、考えられる２６個のビット組み合わせのそれぞれが、Cからの語のうちで一回生起することが分かる。完全にするために、前述の制限と同様な、xに対する制限によっても、適切な符号Cが得られる。実際に、何れかのa∈｛0,1｝について、かつ、何れかのb∈｛0,1｝について、Ca,bを、形式(x,x,…,x)の語全てを有している符号とする。ここで、x=(x0,x1,…,x7)は、
x0+x1+x2+x3≡a（mod2）であり、x4+x5+x6+x7≡b(mod2)
であるようなものである。何れかのa及びbについて、Ca,bが、所望の目的に適した符号であることは容易に分かる。
【０１４０】
次に、符号化を、図１３に示す簡易な流れ図を用いることによって説明する。Gを、Eの生成器行列（その一番上の行において１のみを有している）とする。k-1バイトを有する列mは、nバイトの列に符号化される。符号化は２つの工程を有する。
【０１４１】
S11：mを、符号語d(m)=(0,m)Gに符号化する。
【０１４２】
S12：x0,x1,x2,x3及びx4,x5,x6,x7における1の数が偶数である、適切に選ばれたバイトx=(x0,x1,…,x7)について、mが、d(m)+(x,x,…,x)に符号化される。mが、符号Eからの語に符号化されることが分かる。
【０１４３】
図１４の簡易な流れ図に示す復号化は、Eの復号器によって容易に行うことが可能である。受信チャネル語rのECC復号化（工程S21）後の語がw=(w1,w2,…,wn）に等しいことが分かる。次いで、復号化メッセージmが、分離工程（S22）及びマッピング解除工程（S23）によって、式
w=(w1,w1,…,w1)+(0,m)G
から求められる。Gが恒等行列を有する場合（通常そうであるように）、mは、恒等行列に相当する位置における一連のバイトに等しいに過ぎない。
【０１４４】
図１５は、本発明による復号器の構成図を示す。この図は、その最も左のk+1位置において組織的な、(n,k+1)ECC符号（符号語長n、寸法k+1）の場合の分離及びマッピング解除の工程も示す。スクランブル符号語の選択は、最も左の情報シンボルによって明らかにされる。メッセージmは、後続するk個の情報シンボルを有する。分離装置８００の、一方の出力（すなわち、（w1,w1,…,w1））は、（反復符号Cからの）スクランブル符号語を表す。分離装置８００の、他方の出力は、中間系列（すなわち、(0,w2-w1,wn-w1)）であり、ECC復号器７００の出力(w1,w2,…,wn)からスクランブル符号語（w1,w1,…,w1）を減算することによって生じる。最後に、マッピング解除装置９００は単に、中間系列iからの最も左のシンボル、並びにECCパリティ・シンボルを除去して、長さkのメッセージ・シンボル系列mを得る。
【０１４５】
この方法を施すことが可能であるためには、全て1の語を符号Eが有することが必要である。このことは、Eが、長さK−1の、Fqにわたるリードソロモン符号である場合にあてはまる一方、q−1よりも短い長さKのリードソロモン符号の場合にはあてはまるものでない。軽微な修正によって、[n,k]短縮リードソロモン符号Eを、全て１の語を有する符号に変換することが可能である。実際に、a=(a1,a2,…,an)を、i=1,2,…,nの場合にai≠0であるような、Eからの語とする（これは常に存在する）。次に、一般化されたリードソロモン符号Eaを、Ea=｛（c1/a1,c2/a2,…,cn/an）/（c1,c2,..cn）∈E｝によって表す。Eはaを有するので、全て１の語はEaにある。Eの符号器Ψのものが廃棄されているものとすれば、情報バイト列をEa内の語に符号化する幾分明白な方法が２つ存在する。
【０１４６】
第１の代替策は、情報列をΨに供給し、次いで、i番目のシンボルをaによって除算するものである。第２の代替策の場合、Ψが組織的符号器であるものとする。位置iに対応する情報シンボルは、aiによって乗算することが可能であり、修正された情報ストリームはΨに供給することが可能である。Ψによって生成されるパリティ・シンボルは、ajによって（jの適切な値について）除算される。情報シンボルは、変更されずに（すなわち、aiとの乗算なしで）記録される。
【０１４７】
明らかに、符号化のやり方を復号器は分かっていなければならない。Eaに対する復号化は、まず、受信された語のi番目のシンボルをaiと乗算することにより、かつ、後に、Eに対して復号器を施すことにより、行うことが可能である。Eから得られた語のi番目のシンボルをaiによって除算することにより、Ea内の対応する語が得られる。情報シンボルのみを対象としており、符号化が、組織的なやり方で行われている場合、除算は行わなくてよい。
【０１４８】
又、中央ビットを近傍に備える場合、前述の方法の結果からの単純な修正を用いることが可能である。形式(x,x,…,x)の語全ての集合をスクランブル符号として用いることを提案する。ここで、x=(x0,x1,…,x7)は、「1」に設定されたビットを偶数、有する。[8,7,2]符号における7個の位置の何れも平衡集合を構成しており、（中央ビットをはじめとする）近傍におけるビットは全て、別々のカラーを有しているので、上記定理をなお適用することが可能である。この場合には、Cは、27=128語を有している。
【０１４９】
米国特許第5,671,236号明細書及び米国特許第5,854,810号明細書記載の、Denissen及びTolhuizenによる、このいわゆるラムダ・トリックを用いれば、スクランブル方法を、全て１の語を有するバイト指向誤り訂正符号と効率的に組み合わせることが可能である。リードソロモン符号の単純な修正（全て１の語を修正符号内に強制的に入れる）を提案する。本発明の上記提案スクランブル符号を、全て１の符号語の倍数とみなし得ることによって、「ラムダ・トリック」を用いることが容易になり得る。この「ラムダ・トリック」の更なる詳細に関しては、内容を本明細書及び特許請求の範囲に援用する前述の米国特許第5,671,236号明細書及び米国特許第5,854,810号明細書を参照のこと。
【０１５０】
図１６を用いることによって、ラムダ・トリックの利用を示すことが可能である。スクランブル符号Cをサブ符号として有する（すなわち、Cの各語がC’からの語である）誤り制御符号C’を検討する。符号C’はm=|C’|/|C|集合（例えば、それぞれが|C|個の語を有するA1,A2,….,Aｍ（ここでは、|A|は集合Aの要素の数を表す））に分割される。図１６では、前述の集合それぞれを|C|個の行のブロックとして表す。符号化することが可能なメッセージの数はmに等しい。メッセージ毎に、符号器がこのメッセージをAjからの語に符号化するような指数jが存在している（すなわち、メッセージは、その符号化バージョンが存在するブロックによって判定される）。符号器は、オブジェクティブ関数を最適にするために、Ajにおいて選ぶ符号語を選ぶ。
【０１５１】
Cが、C’のサブ符号の任意のコセットである場合に同じ原理があてはまることは当業者に明らかである。
【０１５２】
復号器はまず、受信された語を、C’からの符号語cに復号化する。次いで、cがAjにあるような指数jを求める。「マッピング解除」工程では、送信メッセージがjから取り出される。
【０１５３】
好ましい実施例では、各AjはCのコセットである。すなわち、j毎に、Ajからの各語が、特定のスクランブル語cからの形式cj+cのものであるような符号語cjが存在する。すなわち、Aj=｛cj+c|c∈C｝である。この好ましい実施例によって、（前述の）特定のメッセージに対応するコセットを符号器が効率的に判定することが可能になる。これによって、単純なやり方で符号化メッセージに符号語のマッピング解除を復号器が行うことが可能になる。
【０１５４】
前述の通り、C’はCをサブ符号として有することを提案する。この好ましい実施例では、Cの反復符号を選ぶ。しかし、各リードソロモン符号C’が反復符号を有する訳でない。（前述の）通常のリードソロモン符号の軽微な修正によって、リードソロモン符号の利点（等しい誤り訂正能力、ほぼ同じ符号化処理及び復号化処理）全てを備える一方、反復符号を有する符号C’’がもたらされる。
【０１５５】
結論付ければ、上記提案される本発明は、特定の点（時間及び／又は空間において）での記憶チャネル又は送信チャネルのビット誤り確率を、特定の点の近傍におけるチャネル入力の関数として、かつその点自体でのチャネル入力の関数として表すことが可能であることを前提としている。更に、特定のストリームにおけるチャネル出力全てにわたる期待ビット誤りレートは、ストリームにわたる、特定の関数の平均として表すことが可能である。上記提案されたスクランブル方法には、小さなスクランブル符号Cから適切に選ばれたスクランブル符号語の、q（2進：q＝２）を法とする加算が関係する（これは、誘導スクランブルとも呼ばれる）。前述の通り、（予測）ビット誤りレート（シンボルの予測ビット誤り確率の平均）の代わりに、本発明を、局所関数（こうした局所関数は、特定の格子位置の近傍位置のみによって変わってくる）の平均として、表す、又は近似することが可能な他の関数に同様に適用することが可能である。前述の代替的なフィギュア・オブ・メリットの例として、単純な線形フィルタリング処理後の累乗（すなわち、二乗値）（すなわち、フィルタの出力の累乗）がある。
【０１５６】
本発明によれば、メッセージにｃ＊が付加されることによって、予測ビット誤りレートが、一様なランダム入力のその期待値を超えることが決してないことになるようなスクランブル符号語ｃ＊が常に存在するような、スクランブル符号Cに対する十分条件が設けられる。
【０１５７】
チャネル・データ・ストリームの上記提案タイリングを用いれば、サーチする対象の符号数がわずかしかない、2次元光記憶に用いるような2次元チャネルに対する前述の条件を満たすスクランブル符号Cを構成することが可能である。上記提案誘導スクランブル方法を誤り訂正符号と組み合わせるうえでのいくつかのやり方を示している。示している可能性のうち、ラムダ・トリックの利用が、好ましい手法である。
【０１５８】
本発明による符号化方法の利用は、記録担体上に記憶される、又は送信回線を介して信号として送信されるチャネル・データ・ストリームの出力信号からも検出可能である。通常の記録担体の場合、チャネル・データ・ストリームの第１のシンボルが符号器の出力に一致する確率は存在するが、わずかである。実際には、ストリームは、それぞれが符号語を備える数千又は数百万の連続したブロックを有している。例えば、こうしたブロックの９９％の一部（記録媒体上のチャネル誤りが理由で、100%であることは決してない）について、記録媒体上にみられる、符号語の第１のシンボルの値（又は、一般には、Cからの、考えられるスクランブル符号語のうちの、c_optの選択）が、本発明による符号器によって生成される、雑音なしの符号語の第１のシンボルに一致する確率は零になっている（すなわち、何れの記録アプリケーションにも通常みられるようにブロック数が大きいという理由で、偶然の一致は存在し得るものでない）。通常のブロック長（すなわち、符号語長）は、約「数千バイト」である。通常の記録媒体は、ギガバイト又はそれ以上を有している。要約すれば、本発明に従っていない記録媒体の場合、符号器に、記録媒体上に記憶されたユーザ・データ・ストリームが供給されると、スクランブル符号語に対応する選択が、偶然を超える可能性で、記録媒体上で検出することが可能な、スクランブル符号語の選択に一致することになるような、本発明における符号器を構成することが可能でないことになる。
【０１５９】
よって、本発明による符号化方法の利用を検出するために、以下の工程を施すことが可能である。
【０１６０】
(1)符号化データ・ストリーム（ディスク毎に数千ブロック）を取り出す工程、及び
(2)本発明による上記方法による、データ・ストリームを再符号化する工程。
【０１６１】
こうした再符号化データ・ストリームが、「多くの場合に、」ディスク上に記録されたストリームと一致する場合、当該符号化方法が用いられている可能性は、ほぼ１である。
【０１６２】
次に、本発明の更なる実施例を記載する。こうした実施例では、拡張装置がない状態にまで、拡張装置を示すことを控えており、用いるスクランブル符号語の選択は、別個の手段によって受信器に伝達しなければならない。
【０１６３】
スクランブル符号語シンボル・ストリーム(c）の集合Cによって、ユーザ・データ・シンボル・ストリーム(m)をチャネル・シンボル・データ・ストリーム(b)に符号化する符号化装置の実施例において、シンボル・ストリームは、Iの部分集合Jの収集体X、及び、すなわち、ストリーム毎（大局）フィギュア・オブ・メリット関数（G）を用いて、シンボル入力位置集合I上で規定される、順序付けされたシンボル値集合であり、
少なくとも１つの符号語が、少なくとも２つの別々のシンボル値を備え、
部分集合JはCの平衡部分集合であり、
ストリーム毎フィギュア・オブ・メリットGは、（Xからの）部分集合J全てに対して求められるシンボル値の局所フィギュア・オブ・メリット関数（テーブル）gの値の線形的な組み合わせであり、
上記符号化装置は、
ユーザ・データ・シンボル・ストリーム(m)に符号語(c’)をマッピングした結果の、ストリーム毎フィギュア・オブ・メリット関数（G）の値(v)を判定する処理装置と、
ユーザ・データ・ストリーム(m’)への符号語(c’)のマッピングの、ストリーム毎メリット値(v)から最適なストリーム毎メリット値（v_opt）を選択し、対応する最適スクランブル符号語(c_opt)を選択するために最適メリット値（v_opt）を用いる選択装置と、
（雑音のある）チャネル（L）への入力シンボル・ストリーム(b)としての役目を担うための、ユーザ・データ・ストリーム(m)に、最適な符号語(c_opt)をマッピングした結果から生じる、マッピングされたユーザ・データ・ストリーム(m’_opt)を得るマッピング装置（スクランブル装置としても知られる）とを備える。
【０１６４】
この実施例は、
入力位置集合（I）が格子構造を有し、
収集体（I）が、入力位置（Iにおけるi）全ての集合の（部分集合）の近傍位置(i-N)の、順序付けされた集合の収集体であり、
符号（C）が、線形符号のコセットであり、
符号（C）のサイズが少なくとも４である点で更に改良することが可能である。
【０１６５】
更なる実施例は、スクランブル符号（C）が少なくとも一次元において巡回的である点で改良されている。
【０１６６】
符号装置は、スクランブル符号（C）が、特定の次元(k)の反復符号であり、
指数集合（I）が、部分集合(Iu)のいくつか（U）に分割され、符号(k)の次元が高々、部分集合（U）の数に等しく、
収集体（X）における部分集合（J）全てについて、集合（J）における別々の指数(i)は全て、Iの別個の部分集合（Iu’）に備えられる点で更に改良される。
【０１６７】
空でない符号（C）の指数集合（I）からの特定のサイズ（J）の入力位置（J）の平衡部分集合を、符号化装置に用いることが可能である（ここで、スクランブル符号（C)からのスクランブル符号語(c)の、指数部分集合（J）への制限は多数回、等しく生起する（長さ(j)の考えられる系列は全て、平衡部分集合（J）のサイズに等しい）。
【０１６８】
符号化装置は、部分集合(i−N)のシンボル値（ｙ）の、順序付けされた部分集合の局所フィギュア・オブ・メリット関数（ｇ）が、チャネル入力シンボル（ｙ）の前述の順序付けされた部分集合によって、指数(i)でのチャネル入力についてチャネル（L）によって明らかにされた推定情報量（P）の関数であり、最適メリット値(v_opt)が最大メリット値である点で更に精緻化することが可能である。
【０１６９】
更なる改良は、チャネルによって明らかにされる推定情報量（P）が、指数(i)での期待シンボル誤りレートである点である。
【０１７０】
更なる改良は、近傍(i−N)におけるフィルタ入力シンボルの順序付けされた部分集合を前提とすれば、局所フィギュア・オブ・メリット関数(g)が、出力指数(i)でフィルタの出力の累乗である点で達成することが可能である。
【０１７１】
符号器を改良するために、部分集合(i−N)上のチャネル入力シンボル（ｙ）の順序付けされた部分集合によって、指数(i)でのチャネル入力についてチャネル（L）によって明らかにされる推定情報量（P）は、部分集合(i−N)にない指数(i’)でのシンボルの値にわたって最小にされる。
【０１７２】
符号器を改良するために、ユーザ・データ・シンボル・ストリーム(m)に符号語(c’)をマッピングした結果の、ストリーム毎フィギュア・オブ・メリット関数（G）の値(v)を判定する処理装置は、ヒストグラム集合を用いる。
【０１７３】
符号器を改良するために、スクランブル符号（C）は、ユーザ・データ・シンボル・ストリーム(m)が符号化される誤り制御符号（C’）のサブ符号である。
【図面の簡単な説明】
【０１７４】
【図１】別々の光チャネル読み出し（HF）信号レベルを示す6角形格子上の2次元符号の概略的な信号パターンを示す図である。
【図２】別々のクラスタ・タイプを示す6角形格子上の2次元符号の概略的な信号パターンを示す図である。
【図３】符号化システムの概括的なレイアウトを示す構成図である。
【図４】ストリップ・ベースの2次元符号化手法を示す概略図である。
【図５】本発明による符号化装置の概括的なレイアウトを示す構成図である。
【図６】図５に示す符号化装置の詳細を示す図である。
【図７】本発明による、スクランブル符号語を生成する線形帰還シフト・レジスタを示す図である。
【図８】ヒストグラムを用いた本発明による符号化装置の実施例を示す構成図である。
【図９】図８に示す符号化装置の詳細を示す図である。
【図１０】チャネル・シンボルへのラベルの割り当てを示す2次元チャネル・データ・ストリームの一部を示す図である。
【図１１】2次元チャネル・データ・ストリームへのスクランブル符号語のマッピングを示す図である。
【図１２】1次元チャネル・データ・ストリームへのスクランブル符号語のマッピングを示す図である。
【図１３】符号化方法の別の実施例を示す単純な流れ図である。
【図１４】復号化方法の別の実施例を示す単純な流れ図である。
【図１５】復号化方法の更に別の実施例を示す単純な流れ図である。
【図１６】好ましい実施例における、いわゆるラムダ・トリックの利用を説明する図である。
【図１】
2008502085.tif 000040
【図２】
2008502085.tif 000041
【図３】
2008502085.tif 000042
【図４】
2008502085.tif 000043
【図５】
2008502085.tif 000044
【図６】
2008502085.tif 000045
【図７】
2008502085.tif 000046
【図８】
2008502085.tif 000047
【図９】
2008502085.tif 000048
【図１０】
2008502085.tif 000049
【図１１】
2008502085.tif 000050
【図１２】
2008502085.tif 000051
【図１３】
2008502085.tif 000052
【図１４】
2008502085.tif 000053
【図１５】
2008502085.tif 000054
【図１６】
2008502085.tif 000055
【国際調査報告】
2008502085.tif 000056
2008502085.tif 000057
2008502085.tif 000058