(57)【特許請求の範囲】
【請求項１】
ｎビットの入力データを、所定の拘束条件のもとで冗長ビットを含むＮビットの符号に変換する符号化方法であって、
ｎビットのデータを受け付けて、初期化を行うステップと、
受け付けたｎビットのデータに対するインデクスを決定するインデクス決定ステップと、
前記拘束条件のもとで定められるトレリス線図において、次時点のある状態を始点とした場合に前記トレリス線図において終点に至るまでにとり得るパスの総数を次時点の当該状態の重みと定義し、その重みあるいはそれに近似する値を数値計算する重み算出ステップと、
現時点から次時点への状態の遷移をインデクスと次時点の状態の重みあるいはそれに近似する値とに基づいて、現時点の状態から続く複数のパスのうちいずれか１つを選択することにより決定するパス決定ステップと、
決定されたパスに対して予め割り当てられた値を符号のシンボル値を決定するシンボル値 決定ステップと、
決定されたパスに基づいてそのパスが所定の条件に当てはまる場合にインデクスを正規化する正規化ステップと、
パス決定ステップにおいて決定したパスに従って状態を次時点に遷移させて状態を更新する状態更新ステップと、
重み算出ステップから状態更新ステップまでをＮ回繰り返す繰り返しステップと、
決定ステップで決定された数値の列を符号として出力する符号出力ステップと
を含んでなる符号化方法。
【請求項２】
所定の拘束条件のもとで冗長ビットを含んで符号化した符号を、もとのｎビットのデータに復号する復号方法であって、
符号を受け付けて、初期化を行うステップと、
前記拘束条件のもとで定められるトレリス線図において前記符号に含まれる個々の時点に対応するビットの シンボル値に応じて該トレリス線図上で状態が右へと１時点進むパスを特定するパス特定ステップと、
トレリス線図において時点ｋのある状態を始点とした場合にとり得る全ての終点に至るまでのパスの数をその時点ｋにおける当該状態の重みとして定義し、前記特定したパスについて、現時点に対応する符号内の数値が所定の値であることによって切り捨てられるパスに続く状態の重みあるいはそれに近似する値を数値計算する重み算出ステップと、
切り捨てられた重みがある場合にその切り捨てられた重みあるいはそれに近似する値をインデクスに加算するインデクス加算ステップと、
パス決定ステップにおいて選択したパスに従って状態を次の時点に遷移させて状態を更新する状態更新ステップと、
前記パス特定ステップから状態更新ステップまでを符号に含まれている全てのシンボル値 について繰り返すインデクス積算値算出ステップと、
算出したインデクスの値をもとのデータのインデクスとして決定するとともに、もとのデータとそのインデクスとの間の予め定められた関係に基づいて、もとのデータを出力するステップと
を含んでなる復号方法。
【請求項３】
所定の拘束条件のもとで冗長ビットを含んで符号化した符号を、もとのｎビットのデータに復号する復号方法であって、
符号を受け付けるステップと、
前記拘束条件のもとで定められるトレリス線図において、符号に基づいて、その符号に対応する最終状態を決定するステップと、
前記最終状態を出発点として、インデクスをゼロに設定する初期化ステップと、
符号に含まれる個々の時点に対応するビットのシンボル値 に応じて該トレリス線図上で状態が左へ１時点戻るパスを特定するパス特定ステップと、
トレリス線図において時点ｋのある状態を始点とした場合にとり得る全ての終点に至るまでのパスの総数をその時点ｋにおける当該状態の重みとして定義し、前記特定したパスについて、現時点に対応する符号内の数値が所定の値であることによって、時点が一つ戻る際に切り捨てられるパスに続く状態の重みあるいはそれに近似する値を数値計算する重み算出ステップと、
切り捨てられた重みあるいはそれに近似する値がある場合のみにその切り捨てられた重みあるいはそれに近似する値の値をインデクスに加算するインデクス加算ステップと、
パス特定ステップにおいて決定したパスに従って状態を前の時点に遷移させて状態を更新する状態更新ステップと、
前記パス特定ステップから状態更新ステップまでを符号に含まれている全てのシンボル値 について繰り返すインデクス積算値算出ステップと、
算出したインデクスの積算値をもとのデータのインデクスとして決定するとともに、もとのデータとそのインデクスとの間の予め定められた関係に基づいて、もとのデータを出力するステップと
を含んでなる方法。
【請求項４】
重み算出ステップにおいて、ビットシフトを実行することによって２の累乗の値を計算して求め、前記トレリス線図に対応する遷移行列の最大固有値に関連する既に計算され、記憶手段に保存された値を含むルックアップテーブルを用いて、該重み付けを計算するたびに累乗の計算を改めて実行することなく、さらなる２の累乗の値を求め、そして、得られた２の累乗の値とさらなる２の累乗の値と前記遷移行列の固有ベクトルの各成分の値とを用いて、重みあるいはそれに近似する値を数値計算して求めることを特徴とする請求項１ないし３のいずれかに記載の方法。
【請求項５】
ｎビットの入力データを、所定の拘束条件のもとで冗長ビットを含むＮビットの符号に変換する符号化装置であって 、
ｎビットのデータを受け付けて、初期化を行い、そのデータに対するデータ系列内の順位を示すインデクスを算出するインデクス計算部と、
前記拘束条件のもとで定められるトレリス線図において、次時点のある状態を始点とした場合に前記トレリス線図において終点に至るまでにとり得るパスの総数を次時点の当該状態の重みと定義して、その重みあるいはそれに近似する値を数値計算する重み算出部と、
現時点から次時点への状態の遷移をインデクスと次時点の状態の重みあるいはそれに近似する値とに基づいて、現時点の状態から続く複数のパスのうちいずれか１つを選択することにより決定し、決定されたパスに対して予め割り当てられた値を符号のシンボル値として決定し、決定されたパスに基づいてそのパスが所定の条件に当てはまる場合にインデクスを正規化する比較・出力部と、
決定したパスに従って状態を次時点に遷移させて状態を更新する状態更新部と
を備えており、
重み算出から状態更新までをＮ回繰り返すものである符号化装置。
【請求項６】
所定の拘束条件のもとで冗長ビットを含んで符号化した符号を、もとのｎビットのデータに復号する復号装置であって、
符号を受け付けて、初期化を行い、前記拘束条件のもとで定められるトレリス線図において前記符号に含まれる個々の時点に対応するビットのシンボル値に応じて該トレリス線図上で状態が右へと１時点進むパスを特定して、状態更新を行う状態更新部と、
トレリス線図において時点ｋの状態を始点とした場合にとり得る全ての終点に至るまでのパスの総数をその時点ｋにおける状態の重みとして定義し、前記特定したパスについて、現時点に対応する符号内の数値が所定の値であることによって切り捨てられるパスに続く状態の重みあるいはそれに近似する値を数値計算する重み算出部と、
切り捨てられた重みあるいはそれに近似する値がある場合にその切り捨てられた重みあるいはそれに近似する値をインデクスに加算するインデクス計算部と
を備えており、
状態更新からインデクス計算を符号に含まれている全てのシンボル値について繰り返して、最終的なインデクスの積算値に基づいてもとのデータを出力する復号装置。
【請求項７】
所定の拘束条件のもとで冗長ビットを含んで符号化した符号を、もとのｎビットのデータに復号する復号装置であって、
符号を受け付けて、前記拘束条件のもとで定められるトレリス線図において、該符号に基づいて最終時点の状態を特定し、初期化を行う最終状態特定部と、
前記トレリス線図において前記符号に含まれる個々の時点に対応するビットのシンボル値に応じて該トレリス線図上で状態が左へと１時点戻るパスを特定して、状態更新を行う状態更新部と、
トレリス線図において時点ｋの状態を始点とした場合にとり得る全ての終点に至るまでのパスの総数をその時点ｋにおける状態の重みとして定義し、前記特定したパスについて、現時点に対応する符号内の数値が所定の値であることによって切り捨てられるパスに続く状態の重みあるいはそれに近似する値を数値計算する重み算出部と、
切り捨てられた重みがある場合にその切り捨てられた重みの値をインデクスに加算するインデクス計算部と
を備えており、
状態更新からインデクス計算を符号に含まれている全てのシンボル値について繰り返して、最終的なインデクスの積算値に基づいてもとのデータを出力する復号装置。
【請求項８】
重み算出部が、ビットシフトを実行することによって２の累乗の値を計算して求め、前記トレリス線図に対応する遷移行列の最大固有値に関連する既に計算され、記憶手段に保存された値を含むルックアップテーブルを用いて、該重み付けを計算するたびに累乗の計算を改めて実行することなく、さらなる２の累乗の値を求め、そして、得られた２の累乗の値とさらなる２の累乗の値と前記遷移行列の固有ベクトルの各成分の値とを用いて、重みあるいはそれに近似する値を数値計算して求めることを特徴とする請求項５ないし７のいずれかに記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタルデータの符号化方法および復号方法に関し、詳細には、ｎビットの入力データを、所定の拘束条件のもとで冗長ビットを含むコード長Ｎの符号に変換する符号化方法と、前記拘束条件のもとで変換された符号を、元のｎビットのデータに復号する復号方法、さらには、それらの方法を実施する符号化装置と復号装置に関する。
【背景技術】
【０００２】
デジタル方式の伝送又は記録システムでは、入力データを伝送又は記録に適した符号に変換する際に、種々の目的で冗長ビットを付加する 。符号に冗長ビットを持たせる方法として、与えられたｎビットの入力データに対して符号長Ｎの符号が満たすべき一定の規則（constraint）を定め、この規則（以下「拘束条件」という。）のもとで入力データから符号への変換を行う方法が存在する（特許文献１、非特許文献１）。ここで、入力データのビット数ｎと符号の符号長Ｎとの比（＝ｎ／Ｎ）は、符号化率と呼ばれ、Ｎ−ｎ＝Ｋが冗長ビット数となる。拘束条件の下では、この符号化率を理論上可能な最大値（シャノン・キャパシティと呼ばれる。）に近付けるほど、符号化及び復号の手順が複雑となる。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平１１−１８６９１７号公報
【非特許文献】
【０００４】
【非特許文献１】Kees A. Schouhamer Immink, "Codes for Mass Data Storage Systems," Second Edition, published by Shannon Foundation Publishers, Edindhoven, The Netherlands, 2004 (pp. 1-5, 9-10, 20-22, 137-141, 215-218)
【非特許文献２】Lyle J. Fredrickson, "On the Shannon Capacity of DC-and Nyquist-Free Codes", IEEE TRANSACTIONS ON INFORMATION THEORY, VOL37, NO.3, MAY 1991
【発明の開示】
【発明が解決しようとする課題】
【０００５】
上記拘束条件付きの符号化については種々の技術が存在するが、そのうちキャパシティに近い符号化率を達成するための方法の１つとして、数え上げ符号化（enumerative coding）がある。この方法では、ｎビットの入力データの取りうる数値全てについて、それぞれの順位を算出し、これをインデクスと定義する。そして、コード長Ｎの符号の集合のうち拘束条件を満たす全ての符号を抽出し、インデクスの集合と、抽出した符号の集合との間に１対１の対応関係を付与しておくことで、実際の信号処理に際し、この対応関係に基づいて符号への変換及び入力データへの復号を実行する。ここで、インデクスと符号との対応関係は、ルックアップテーブルによって規定することができる。しかしながら、このルックアップテーブルによる対応付けの方法は、入力データのビット数が大きくなると困難になる。例えば、入力データが２００ビット（ｎ＝２００）である場合は、上記ルックアップテーブルにおいて、２の２００乗の数の対応関係を設定しておく必要が生じることから、その実現は、技術的に困難である。
【０００６】
また、数え上げ符号化においては、ある拘束条件の下で、トレリス線図を用いて符号化と復号を行うことが行われる。このときには、ルックアップテーブルの他にも、トレリス線図上のパスの総計と、トレリス線図上の各状態から最終状態までのパス数に基づく重みが計算上必要になる。例えば、Ｎ＝４０００ともなると、拘束条件として１７個の状態を取りうるトレリス線図を考えると、その重みを保存するために必要なメモリーは、４０００＊（２＊８＋１）＊４０００＝３０ＭＢにも達するため、ハードウエアの制約上実現することは不可能であるといえる。
【０００７】
本発明は、数え上げ符号化において、入力データのインデクスと符号との対応関係を計算できるようにし、対応付けのためのルックアップテーブルを不要とし、重みを予め算出して保存しておくことを不要とすることを目的とする。
【課題を解決するための手段】
【０００８】
本発明に係る符号化方法は、ｎビットの入力データを、所定の拘束条件のもとで冗長ビットを含むＮビットの符号に変換する符号化方法であって、ｎビットのデータを受け付けて、初期化を行うステップと、受け付けたｎビットのデータに対するインデクスを決定するインデクス決定ステップと、前記拘束条件のもとで定められるトレリス線図において、次時点のある状態を始点とした場合に前記トレリス線図において終点に至るまでにとり得るパスの総数を次時点の当該状態の重みと定義し、その重みあるいはそれに近似する値を算出する重み算出ステップと、現時点から次の時点への状態の遷移をインデクスと次時点の状態の重みあるいはそれに近似する値とに基づいて、現時点の状態から続く複数のパスのうちいずれか１つを選択することにより決定するパス決定ステップと、決定されたパスに対して予め割り当てられた値を符号のシンボル値として決定するシンボル値決定ステップと、決定されたパスに基づいてそのパスが所定の条件に当てはまる場合にインデクスを正規化する正規化ステップと、パス決定ステップにおいて決定したパスに従って状態を次の時点に遷移させて状態を更新する状態更新ステップと、重み算出ステップから状態更新ステップまでをＮ回繰り返す繰り返しステップと、決定ステップで決定された数値の列を符号として出力する符号出力ステップとを含んでなる方法である。
【０００９】
また、本発明にかかる第１の復号方法は、所定の拘束条件のもとで冗長ビットを含んで符号化した符号を、もとのｎビットのデータに復号する復号方法であって、符号を受け付けて、初期化を行うステップと、前記拘束条件のもとで定められるトレリス線図において前記符号に含まれる個々の時点に対応するビットのシンボル値に応じて該トレリス線図上で状態が右へと１時点進むパスを特定するパス特定ステップと、トレリス線図において時点ｋのある状態を始点とした場合にとり得る全ての終点に至るまでのパスの総数をその時点ｋにおける当該状態の重みとして定義し、前記特定したパスについて、現時点に対応する符号内の数値が所定の値であることによって切り捨てられるパスに続く状態の重みあるいはそれに近似する値を算出する重み算出ステップと、切り捨てられた重みあるいはそれに近似する値がある場合にのみその切り捨てられた重みあるいはそれに近似する値の値をインデクスに加算するインデクス加算ステップと、パス特定ステップにおいて特定したパスに従って状態を次の時点に遷移させて状態を更新する状態更新ステップと、前記パス特定ステップから状態更新ステップまでを符号に含まれている全てのシンボル値について繰り返すインデクス積算値算出ステップと、算出したインデクスの値をもとのデータのインデクスとして決定するとともに、もとのデータとそのインデクスとの間の予め定められた関係に基づいて、もとのデータを出力するステップとを含んでなる方法である。
【００１０】
さらに、本発明にかかる第２の復号方法は、所定の拘束条件のもとで冗長ビットを含んで符号化した符号を、もとのｎビットのデータに復号する復号方法であって、符号を受け付けるステップと、前記拘束条件のもとで定められるトレリス線図において、符号に基づいて、その符号に対応する最終状態を決定するステップと、前記最終状態を出発点として、インデクスをゼロに設定する初期化ステップと、符号に含まれる個々の時点に対応するビットのシンボル値に応じて該トレリス線図上で状態が左へ１時点戻るパスを特定するパス特定ステップと、トレリス線図において時点ｋのある状態を始点とした場合にとり得る全ての終点に至るまでのパスの総数をその時点ｋにおける当該状態の重みとして定義し、前記特定したパスについて、現時点に対応する符号内の数値が所定の値であることによって、時点が一つ戻る際に切り捨てられるパスに続く状態の重みあるいはそれに近似する値を算出する重み算出ステップと、切り捨てられた重みあるいはそれに近似する値がある場合にのみその切り捨てられた重みあるいはそれに近似する値をインデクスに加算するインデクス加算ステップと、パス決定ステップにおいて選択したパスに従って状態を前の時点に遷移させて状態を更新する状態更新ステップと、前記パス特定ステップから状態更新ステップまでを符号に含まれている全てのシンボル値について繰り返すインデクス積算値算出ステップと、算出したインデクスの値をもとのデータのインデクスとして決定するとともに、もとのデータとそのインデクスとの間の予め定められた関係に基づいて、もとのデータを出力するステップとを含んでなる方法である。
【００１１】
これらの本発明の符号化または復号方法においては、重み算出ステップにおいて、ビットシフトによる２の累乗の計算と、前記トレリス線図に対応する遷移行列の最大固有値に関連する既に計算され、記憶手段に保存された値を含むルックアップテーブルと、前記遷移行列の固有ベクトルとを用いて重みを算出することができる。
【００１２】
更に本発明は符号化装置および復号装置にも関する。本発明の符号化装置は、ｎビットの入力データを、所定の拘束条件のもとで冗長ビットを含むＮビットの符号に変換する符号化装置であって、ｎビットのデータを受け付けて、初期化を行い、そのデータに対するデータ系列内の順位を示すインデクスを算出するインデクス計算部と、前記拘束条件のもとで定められるトレリス線図において、次時点のある状態を始点とした場合に前記トレリス線図において終点に至るまでにとり得るパスの総数を次時点の状態の重みと定義して、その重みあるいはそれに近似する値を算出する重み算出部と、現時点から次時点への状態の遷移をインデクスと次時点の状態の重みあるいはそれに近似する値とに基づいて、現時点の状態から続く複数のパスのうちいずれか１つを選択することにより決定し、決定されたパスに対して予め割り当てられた値を符号のシンボル値として決定し、決定されたパスに基づいてそのパスが所定の条件に当てはまる場合にインデクスを正規化する比較・出力部と、決定したパスに従って状態を次の時点に遷移させて状態を更新する状態更新部とを備えており、重み算出から状態更新までをＮ回繰り返すものである符号化装置である。
【００１３】
また、本発明の第１の復号装置は、所定の拘束条件のもとで冗長ビットを含んで符号化した符号を、もとのｎビットのデータに復号する復号装置であって、符号を受け付けて、初期化を行い、前記拘束条件のもとで定められるトレリス線図において前記符号に含まれる個々の時点に対応するビットのシンボル値に応じて該トレリス線図上で状態が右へと１時点進むパスを特定して、状態更新を行う状態更新部と、トレリス線図において時点ｋの状態を始点とした場合にとり得る全ての終点に至るまでのパスの数をその時点ｋにおける状態の重みとして定義し、前記特定したパスについて、現時点に対応する符号内の数値が所定の値であることによって切り捨てられるパスに続く状態の重みあるいはそれに近似する値を算出する重み算出部と、切り捨てられた重みあるいはそれに近似する値がある場合にその切り捨てられた重みあるいはそれに近似する値をインデクスに加算するインデクス計算部とを備えており、状態更新からインデクス計算を符号に含まれている全てのシンボル値について繰り返して、最終的なインデクスの積算値に基づいてもとのデータを出力する復号装置である。
【００１４】
更に、本発明の第２の復号装置は、所定の拘束条件のもとで冗長ビットを含んで符号化した符号を、もとのｎビットのデータに復号する復号装置であって、符号を受け付けて、前記拘束条件のもとで定められるトレリス線図において、該符号に基づいて最終時点の状態を特定し、初期化を行う最終状態特定部と、前記トレリス線図において前記符号に含まれる個々の時点に対応するビットのシンボル値に応じて該トレリス線図上で状態が左へと１時点戻るパスを特定して、状態更新を行う状態更新部と、トレリス線図において時点ｋの状態を始点とした場合にとり得る全ての終点に至るまでのパスの数をその時点ｋにおける状態の重みとして定義し、前記特定したパスについて、現時点に対応する符号内の数値が所定の値であることによって切り捨てられるパスに続く状態の重みあるいはそれに近似する値を算出する重み算出部と、切り捨てられた重みあるいはそれに近似する値がある場合にその切り捨てられた重みあるいはそれに近似する値をインデクスに加算するインデクス計算部とを備えており、状態更新からインデクス計算を符号に含まれている全てのシンボル値について繰り返して、最終的なインデクスの積算値に基づいてもとのデータを出力する復号装置である。
【００１５】
これらの符号化装置または復号装置においては、重み算出部が、ビットシフトによる２の累乗の計算と、前記トレリス線図に対応する遷移行列の最大固有値に関連する既に計算され、記憶手段に保存された値を含むルックアップテーブルと、前記遷移行列の固有ベクトルとを用いて重みあるいはそれに近似する値を算出するものとすることができる。
【発明の効果】
【００１６】
本発明によれば、入力データから符号への変換において、トレリス線図上で状態が遷移していくパスを指標として、各状態から次の状態への重みを当該状態から最終の状態のいずれかまでのパスの総数に対応する重みの値を数値計算し、この計算された重みの値に基づいて、ある入力データのインデクスから符号を求める。符号化の過程で実行されるこの重みの計算が本発明においては重要となる。本発明においては、トレリス線図上の各状態からのパスの総数をカウントしたり、記憶して用いることはない。また、もとのデータと符号の直接的な対応付与のためのルックアップテーブルを用いることもない。これにより、状態が遷移するパスに基づいて入力データのインデクスと符号との対応関係を決定することが可能となるので、もとのデータと符号の直接的な対応付与のための、非常に大きなものとなるルックアップテーブルが不要となり、拘束条件下にあって、入力データの桁数が相当大きな場合でも、パスの選択という比較的簡単な手法によって高い符号化率を達成することができる。
【００１７】
同様に、符号からもとのデータへの復号では、トレリス線図上で状態が遷移するパスを、入力した符号内の数値に基づいて特定することが可能である。従って、符号への変換に際して切り捨てられるパスの数（重み）に基づいて符号ともとのデータのインデクスとの対応関係を判断し、符号ともとのデータの直接的な対応付与のための非常に大きなルックアップテーブルによらずに、もとのデータのインデクスを算出して、復号を達成することができる。本発明によれば、重みは数値計算する。重みを得るために、各状態についてパスをカウントしたり、パスの総数を記憶して用いる必要はない。
【図面の簡単な説明】
【００１８】
【図１】本発明の第１の実施形態に係る符号化装置の構成を示すブロック図
【図２】同実施形態に係る符号化と復号の処理の概念を示す説明図
【図３】同実施形態に係る入力データ、順位識別インデクス及び符号の対応関係を概念的に示す説明図
【図４】同実施形態に係る符号化のためのトレリス線図
【図５ａ】同実施形態に係る符号化処理を概念的に示す説明図（時点１，２、３への遷移）
【図５ｂ】符号化処理の説明図（時点４への遷移）
【図５ｃ】符号化処理の説明図（時点５，６への遷移）
【図６】符号化処理の流れを示すフローチャート
【図７】重みの計算方法を示すフローチャート
【図８】トレリス線図に関する遷移行列の説明図
【図９】本発明の第２の実施形態に係る実施形態に係る復号処理の流れを示すフローチャート
【図１０】本発明の第２の実施形態に係る復号装置の構成を示すブロック図
【図１１】本発明の第３の実施形態に係る復号処理の流れを示すフローチャート
【発明を実施するための最良の形態】
【００１９】
以下に図面を参照して、本発明の実施の形態について説明する。
【００２０】
図１は、本発明の第１の実施形態に係る符号化装置の構成を示すブロック図である。本実施形態では、図２にその概要を示すｎビットの入力データｉを、所定の拘束条件（constraint）のもとでＫビットの冗長ビットを含むコード長Ｎの符号ｃに変換する（Ｎ＝ｎ＋Ｋ）。
【００２１】
図１に示すインデクス算出部１１１は、入力データｉを受け付けて、この入力データｉのインデクスＩを算出する。インデクスＩは、ｎビットの入力データｉの並びにおける順番を示す。本実施形態では、例えば、インデクスＩとして、入力データｉの十進数換算値（＝０〜２ｎ−１）を採用する。 ここで、入力データｉの十進数換算値を採用しているのは、十進数の方が説明のためにわかりやすいからであり、実際の演算においては順位付けのためのインデクスとして入力データｉをそのまま使用することができる。
【００２２】
図３は、入力データ（長さｎビット）と、入力データの十進数換算値と、符号（長さＮ）との関係を、本実施形態について示している。ここで、ｎビットの入力データとＮビットの符号は、一般的には、それぞれｎ個とＮ個のシンボル値の列として表現されるものである。シンボル値の代表的な例として２進値があることはいうまでもなかろうが、２進値に限定されるものでもない。本明細書ではシンボル値が２進値の場合を例に説明する。Ｕ（ｉ）は、ｎビットの入力される可能性のある２進数データを並べた列を示す。Ｉ（ｉ）は、このｎビットの入力データの十進数換算値の列を示している。列Ｉ（ｉ）に対して各換算値の脇に示す１〜２ｎの表示は、十進数換算値＝０を先頭とした増方向の順位であり、これをインデクスＩと呼ぶ。入力データｉの十進数換算値が０の場合にインデクスＩも０となり、十進数が増大するに従ってインデクスＩは増大していく。
【００２３】
図３に例示するように、例えば、全てゼロの値からなるｎビットの入力データがあったとき、それに対応するＮビットの符号は、冗長性を付与するために、何らかの規則に基づいて０または１が付加されている。 同様に、Ｕ（ｉ）の最後にある全てが１の入力データに対する符号には付加的な０または１が含まれている 。そして、Ｎビットの符号には入力データとの対応関係がないｍ個の符号が含まれている。拘束条件を満たすＮビットの符号列（図３）をＣ（Ｍ，Ｎ）と呼ぶ。Ｍは拘束条件に関連した定数を表すものであり、Ｎは上と同じように冗長性が加わった符号のビット数である。そして、符号化と復号は、インデクスを介した、入力データ列とＣ（Ｍ，Ｎ）の要素との対応付けによって行うことができる。集合Ｃ（Ｍ，Ｎ）にある要素の個数をＰとすると、理論上、Ｐが２のｎ乗の値以上であれば、符号化と復号ができることとなる。そのような条件を満たす最小のＮの値をＮminとすれば、数え上げ符号化の理論限界あるいはシャノン・キャパシティに近い符号化率は、ｎ／Ｎminということになる。  
【００２４】
図４に、本実施形態にかかる拘束条件を表現したトレリス線図を示す。図４のトレリス線図における線の交点は、その時点ｋにおいて取りうる状態Ｓｋを示す。そして、入力データから符号への変換において、ランニングデジタルサム（ＲＤＳ、Running Digital Sum）によって拘束条件を付与する。ＲＤＳは、符号の「１」と「０」にそれぞれ値「＋１」（トレリス線図においては斜め上への遷移を意味する）と値「−１」（同じく斜め右下への遷移を意味する）を対応させて計算できる、符号列の開始点からのこれらの値の総和を表す。具体的には、ＲＤＳの計算は、時点ｋから時点ｋ＋１の遷移に対応する、下記の手順で決定された符号の値が「０」であれば−１を、「１」であれば１を、時点毎に逐次加算していくことによる。換言すれば、ＲＤＳの値を縦軸とするトレリス線図において、ある時点ｋから時点ｋ＋１の遷移に対応する符号の値が「０」である場合は、次時点ｋ＋１に向けて状態ＳｋからＲＤＳを一つ減らす方向（斜め下）にある状態Ｓｋ＋１へと遷移させる一方、「１」である場合は、ＲＤＳを一つ増やす方向（斜め上）に状態Ｓｋを遷移させる。そして、所与の拘束条件により、このＲＤＳの取りうる値を制限している。
【００２５】
図４のトレリス線図が表す拘束条件は、ＲＤＳを＋２から−２の間に制限するものである。ＲＤＳ＝０から出発するとして、入力データに１または０が２回続いたら、その次には、それぞれ０または１を入れるというものである。つまり、ランニングデジタルサム（ＲＤＳ）をＭ＝２とすることで±２の範囲に限定する。
【００２６】
ここでは、例として、Ｎ＝１０として、Ｍ＝２としているが、Ｎ＝１０は説明のために意図的に小さな数をあえて選んだものである。本発明は、Ｎ＝２０以上、数千といった大きなビット数の符号に適用することができるものである。同様にＭ＝２も本発明の範囲を限定するような数値ではまったくない。この例において、Ｃ（２，１０）の要素の合計は、３２４個である。したがって、このＣ（２，１０）を使って、ｎ＝８、２の８乗が２５８であるので、８ビットの入力データを符号化することができることが分かる。
【００２７】
そして、図４中の各交点の近くに記載した数字は、その交点が表す状態Ｓｋを始点とした場合にこの線図においてとり得る終点Ｓ１０のいずれかに至るまでのパスの数を示している。言い換えれば、状態Ｓｋから終点Ｓ１０に至るまでの、時点間のパスセグメントの組み合わせの数である。状態Ｓｋ＋１についてのこのパス数を、状態Ｓｋから状態Ｓｋ＋１への遷移を考える際に重みＷｋとして用いる。例えば、時点０において、状態Ｓ０は、ＲＤＳの定義上、ＲＤＳ＝０の１点にのみ存在し、全ての終点Ｓ１０（ＲＤＳ＝−２，０，２の３つの状態）に至るまでの可能なパスの数（重みＷ０）は３２４である。すなわち、時点ｋ＝０から時点ｋ＝１への遷移を考えるためには、遷移先として状態Ｓ１（−１）と状態Ｓ１（１）があって、それぞれに向けた遷移の重みＷ１（−１）＝１６２とＷ１（１）＝１６２があることになる（Ｗ１のかっこ内はＲＤＳの値ｓを表す）。時点ｋ＝２では、全部で３点の状態Ｓ２（−２）、Ｓ２（０）、Ｓ２（２）（それぞれＲＤＳ＝−２，０，２に対応する）が存在し、時点ｋ＝１から時点ｋ＝２に向けた各状態の重みＷ２は、図面に向かって下からＷ２（−２）＝５４（ＲＤＳ＝−２），Ｗ２（０）＝１０８（ＲＤＳ＝０），Ｗ２（２）＝５４（ＲＤＳ＝２）である。
【００２８】
図４のスタートを見ると、ＲＤＳ＝０から始まるものとして、図４に例示したＣ（Ｍ，Ｎ）の要素であるパスＰ１が００１１１０１１００１１１であるとすると、まず、最初の符号が０なのでＲＤＳ＝−１に遷移し、次の符号がまた０であるので、ＲＤＳ＝−２に遷移する。その後、１が３回続くのでＲＤＳ＝＋１に遷移し、次に０が２回続くので一旦ＲＤＳ＝−１になるが、その後１が３回続くのでＲＤＳ＝２で終わる。このように、Ｐ１は拘束条件を満たすことが改めてわかる。例示したＰ２＝０１１０１１０００１およびＰ３＝１０００１１０１１１についても同様である。そして、このようなＰ１からＰｎを入力データに対応づける。
【００２９】
なお、別の拘束条件としては、非特許文献２において、ＮＲＺ（Non Return to Zero）方式で符号を表した場合に、符号「１」及び符号「０」にそれぞれ値「＋１」及び値「−１」を対応させると共に１ビットおきに値「−１」を乗じた場合の、連続する符号列の開始時点からの総和を表すＡＤＳ（Alternate Digital Sum）とＲＤＳとの双方を考慮したＦＳＴＤも提案されている。このようなＦＳＴＤも本発明の対象となる。また、ＲＬＬ(runlength-limited constraint)や、ＭＴＲ(mazimum transition run constraint)といった拘束条件も同様に利用することができ、より複雑な符号の作成と復号を行うことができる。ＲＬＬ(d,k)という拘束条件は、１と１の間に０の個数が最小ｄ個、最大ｋ個あるように拘束するものである。また、ＭＴＲは、連続変化の１０１０１０あるいは０１０１０１の個数を制限するものであり、ＮＲＺＩ方式におけるＭＴＲ(j; k)は、連続１の個数をｊ個に、連続０の個数をｋに拘束するものである。
【００３０】
比較・出力部１１２は、インデクス算出部１１１によって算出したインデクスＩと、次に述べる重み算出部１１３によって算出した重みＷ（＝Ｗｋ＋１）とを比較し、符号のトレリス線図上で状態を遷移させる際のパスを選択するとともに、選択したパスに対して予め割り当てられた「０」又は「１」の数値を、時点毎に符号の値として出力する。
【００３１】
重み算出部１１３は、上記のトレリス線図について、時点ｋにおいてＲＤＳの値がｓの状態Ｓｋ (s)を始点とした場合にこの線図においてとり得る全ての終点ＳＮに至るまでのパスの総数である重みＷｋを算出する。具体的には、本実施形態に係る符号化装置は、トレリス線図上の状態Ｓｋ(s)についての重みＷｋ(s)を算出する重み算出部１１３を有する。この重み算出部１１３では、トレリス線図に対応して得られる遷移行列Ｔ（遷移行列生成部１２５）と、その遷移行列Ｔについて計算された右固有値の最大のものλmax（最大固有値算出部１２７）と、同じく遷移行列Ｔの固有ベクトルの成分の値Ｒ(s)（本実施形態の拘束条件下ではｓ ＝−２〜２の整数）（固有ベクトル算出部１２６）を用いて、下に説明する計算式により重みＷｋ(s)を計算することができる。パラメータ算出部１２１は、これらの遷移行列生成部１２５と、固有ベクトル算出部１２６、最大固有値算出部１２７からなるものであるが、これは、本発明の装置の一部とする必要は必ずしもない。設定した拘束条件に対応して、遷移行列が決定し、その遷移行列の固有ベクトルと最大固有値を予め求めておいて、重みの数値計算に用いることができる。ここで、上記比較出力部１１２は、重み算出部１１３から次時点ｋ＋１における状態の重みＷｋ＋１を受け付けて、インデクスＩと入力した重みＷｋ＋１とを比較して、次時点ｋ＋１に向けて状態を遷移させるパスを選択する。
【００３２】
状態更新部１１５は、比較出力部１１２によって選択したパスに従って状態を遷移させ、状態を更新する（状態をＳｋからＳｋ＋１に進める）。
【００３３】
図４は、本実施形態に係る符号のトレリス線図と、３つの異なる符号を出力する際に選択されるパスＰ１〜Ｐ３とを示している。実線によって示すパスＰ１は、符号ｃ１＝（００１１１００１１１）を出力する際のパスであり、点線及び一点鎖線は、符号ｃ２＝（０１１０１１０００１）及び符号ｃ３＝（１０００１１０１１１）を出力する際のパスＰ２，Ｐ３を夫々示している。
【００３４】
上述のように、パスＰ１〜Ｐ３が表す符号 ｃ１〜ｃ３は、いずれもＭ＝２の拘束条件を満たす。例えば、パスＰ１では、時点０においてＲＤＳ＝０であり、符号ｃ１の１ビット目及び２ビット目の数値がいずれも「０」であるから、時点０及び１の状態Ｓ０，Ｓ１のそれぞれについてＲＤＳを一つ減ずる方向のパスが選択される。従って、時点２において、ＲＤＳは−２となる。続く３〜５ビット目では数値が「１」であるから、状態Ｓ２〜Ｓ４について選択されるパスはＲＤＳを一つ増やす方向に切り換わり、時点５までにＲＤＳは１に増加する。そして、６及び７ビット目では再度「０」となり、８ビット目以降では「１」となるから、最終的なＲＤＳの値は２であり、このパスＰ１が表す符号ｃ１は、上記拘束条件を満たす。他の符号Ｐ２，Ｐ３についても同様である。ここで、パスＰ２については時点１でパスＰ１から分離し、パスＰ３については時点０でパスＰ１から分離する。従って、Ｃ（Ｍ，Ｎ）に含まれる拘束条件を満たす全ての符号について、トレリス線図上で異なるパスがあることになる。
【００３５】
ここで、本実施形態に係る符号化装置の動作について、８ビットの入力データ００１０１００１が入力された場合を例に説明する。結論からいえば、符号化装置は、図４のトレリス線図においてパスＰ１に沿って状態を遷移させ、この入力データを符号ｃ１＝（００１１１００１１１）に変換する。
【００３６】
図５ａ〜５ｃは、入力データｉ＝（００１０１００１）を入力した場合における符号化装置（具体的には、比較出力部１１２及び状態更新部１１５）の動作を示している。まず、符合化装置は、入力した入力データｉのインデクスＩを算出する。既に述べたように、インデクスＩは、入力データｉの、０を先頭として数値が増えていく８ビット系列における順位であり、入力データｉの十進数換算値４１である 。
【００３７】
図５ａに示すように、時点０では、ＲＤＳ＝０のところに状態があるが、インデクスＩ＝４１が次の時点１における状態Ｓ１への遷移の可能性は、ＲＤＳ＝１の状態への遷移の可能性を表す重みＷ１（１）が１６２であり，ＲＤＳ＝−１の状態への遷移を表す重みＷ１（−１）も１６２となる。そして、全部で３２４の可能なパスのうちＩ＝４１がどのパスに属するかを判定するために、まずこの３２４のパスを数え上げて、下から１で始めて最上部において３２４で終わるパスを縦に並べた縦の列２０１を作成する。 インデクスI＝４１に対応する列の要素にはハッチを付して図示する。Ｉ＝４１の要素は、列２０１の下部のＷｉ（−１）に対応する１６２個の要素に属するからＲＤＳが一つ減る方向のパスに対応するものと判断する。つまり、時点ｋ＝１への遷移に対応する符号の値であるｃ１（１）はゼロになり、ＲＤＳ＝−１となる。
【００３８】
この列２０１の上半分はもうパスとして通る可能性のないものになっているので、切り捨てて、次の列２０２を作る。すると、この列の要素は、最初の１から１６２までの要素を含むものとなる。状態Ｓ２への遷移を考えると重みはＲＤＳが減る方向へはＷ２（−１）＝５４となり、Ｗ２（０）＝１０８となる。そして、それを要素数１６２の列２０３で表現する。Ｉ＝４１がこの列２０３の下の５４要素と上の１０８要素のどちらに対応するかを列２０２と対応付けてみると、下の５４要素に含まれていることが分かる。このことはＲＤＳが一つ減る方向を取ることを意味するので、時点ｋ＝２への遷移に対応する符号の値ｃ１（２）についてｃ１（２）＝０とする。すると、Ｓ２においては、ＲＤＳ＝−２の状態Ｓ２（−２）にあることになる。列２０３の上部にあるＲＤＳが一つ増える方向への遷移（重みＷ２（０）の側）の可能性はないので、それを切り捨てて、列２０４ができる。
【００３９】
ここで、拘束条件がＭ＝２であるから、これ以上ＲＤＳが減ることはないので、状態Ｓ３（−１）へと遷移する以外になく、ＲＤＳが一つ増える方向へ遷移する。すなわち、ｃ１（３）＝１、ＲＤＳ＝−１となる。
【００４０】
次に、図５ｂを参照して、時点４への遷移を考える。先の遷移は選択の余地がなく行われたので列２０４には変更がない。そして、時点４への遷移の重みは、Ｗ４（−２）＝１８、Ｗ４（０）＝３６となる。これを列で表現すると列２０５になる。列２０５を見るとＩ＝４１は、列２０５の重みＷ４（０）＝３６の側にあることが分かる。ＲＤＳが一だけ増える方向への遷移であるので、ｃ１（４）＝１、ＲＤＳ＝０となる。すると、列２０５の下部は切り捨てることができるので、列２０６ができる。このとき、列２０６の最下端の要素の番号は１９であるので、番号付けを正規化して、最下端が１から始まるように全体の要素の番号を１８だけずらす。すると、列２０７となり、Ｉ＝４１の要素は、０から数えて２４番目（４１−１８＝２３）になる。
【００４１】
図５ｃを見ると、次の遷移の重みは、Ｗ５（−１）＝１８（下部）とＷ５（１）＝１８（上部）となるので、列２０７は列２０８として展開できる。下から２４番目の要素は、Ｗ５（１）の側にあることが分かるので、ｃ１（５）＝１，ＲＤＳ＝１となる。そして、列２０８の下部を切り捨てると、列２０９になる。これを前回と同様、切り捨てた１８要素の分だけ番号付けを正規化すると、列２１０になる。もともとのＩ＝４１に対応する要素は、下から６番目に来る。
【００４２】
そして、次の時点６への遷移を考えると、重みＷ６（０）＝１２（下部）とＷ６（２）＝６（上部）であるので、列２１１となる。Ｉ＝４１に対応する要素は、下部にある。したがって、次の遷移はＲＤＳを減らす方向にあることが分かり、ｃ１（６）＝０，ＲＤＳ＝０となる。
【００４３】
以降は図示しないが、これを繰り返していくと、ｃ１（７）＝０、ｃ１（８）＝１、ｃ１（９）＝１、ｃ１（１０）＝１となって、時点１０ではＲＤＳ＝２となることが分かる。このようにして、Ｉ＝４１の入力データを符号００１１１００１１１に符号化することができる。
【００４４】
図６は、上に説明した本実施形態に係る符号化方法を示すフローチャートである。
【００４５】
Ｓ１１では、初期化として、インデクスＩを算出するとともに、時点ｋを０に、状態をＳ０（０）（かっこ内はＲＤＳの値ｓをゼロに設定したものである。）に設定する。
【００４６】
Ｓ１２では、重み算出部１１３から次時点ｋ＋１における各状態の重みＷｋ＋１を読み込み、インデクスＩの値がＲＤＳが減る方向に続くパスの数である重みＷｋ＋１（ｓ−１）よりも大きいか否かを判定する。Ｗｋ＋１（ｓ−１）よりも大きい場合は、Ｓ１３へ進み、Ｗｋ＋１（ｓ−１）以下である場合は、Ｓ１４へ進む。現時点ｋにおいて状態がＲＤＳ＝−２にあるとき（ｓ＝−２）には、Ｍ＝２の拘束条件があるので、ＲＤＳ＝−３の状態に遷移することはできないので、次の時点ｋ＋１への遷移の重みＷｋ＋１（−３）の値はゼロとなる。Ｗｋ（−２）＝Ｗｋ＋１（−１）である。
【００４７】
Ｓ１３では、ＲＤＳが増える方向に状態が遷移することが分かっているので、符号の対応するビットｃ（ｋ＋１）を「１」に設定し、状態ＳｋをＲＤＳが増える方向のパスに沿って状態Ｓｋ＋１に遷移させる。さらに、ＲＤＳが減る方向のパスを切り捨てたので、インデクスＩの正規化を実行し、インデクスＩのならびから切り捨て分のパスの数に相当する重みＷｋ＋１（ｓ−１）を減算する。ＲＤＳの値ｓはｓ＋１となる。
【００４８】
Ｓ１４では、ＲＤＳが減る方向へ状態が遷移することが分かっているので、符号の対応するビットｃ（ｋ＋１）を「０」に設定し、状態ＳｋをＲＤＳが減る方向のパスに沿って状態Ｓｋ＋１に遷移させる。ＲＤＳの値ｓはｓ−１となる。
【００４９】
Ｓ１５では、時点ｋを１だけ進めるとともに、１を加算したｋが（Ｎ−１）以下であるか否かを判定する。（Ｎ−１）以下である場合は、Ｓ１２へ戻り、（Ｎ−１）よりも大きい場合は、入力データｉに対する符号化処理を終了する。
【００５０】
このように、本実施形態によれば、数え上げ符号化法（enumerative coding method）を採用したことで、拘束条件下にあって、高い符号化率を達成することが可能である。さらに、本実施形態では、入力データのインデクスＩと符号ｃとの対応関係を状態Ｓが遷移するパスに基づいて計算によって判断することとしたので、比較的簡単な手順で符号化処理を行うことができる。本実施形態によれば、インデクスＩと符号ｃの対応関係を決めるためのルックアップテーブルが不要である。
【００５１】
以上で述べた第１の実施形態では、トレリス線図上の重みＷｋ（ｓ）を各時点ｋ（ｋ＝１，２，…，Ｎ）の状態Ｓｋ（ｓ）毎（ｓ＝−２〜２）に分かっているものとして説明した。入力データのビット数が小さい場合には、この重みは予め計算しておいて記憶装置に記憶しておくこともできる。しかしながら、パスの数を数えて得られる重みＷｋ＋１は、本発明者らによって、下に述べるように必要な際に計算によって求めることが可能な「重み系」(Weight System)と呼ぶ数値演算の結果によって置き換えることができることが証明されている。この重み系は、パスカウントに基づく重みであるかそれを近似する値になっている。計算により重み系の数値をその都度求めることにより、記憶しておくべきデータの量を劇的に減らすことができるとともに、必要な数値計算の量も大きく増えることがない。
【００５２】
図１の重み計算部１２１によってそのような計算を行う。まず、図４に示したトレリス線図の基本構造として、図８の左側に示すような状態遷移のパターンを有している。この状態遷移のパターンに対応する遷移行列Ｔが図８の右側に示されている。１は遷移が可能であることを示し、０は遷移が許されていないことを示している。すなわち、この遷移行列Ｔの対角要素は、すべてゼロであり、ある状態から同じ状態への遷移はないことを示している。例えば、行１列２の要素は１であるが、ＲＤＳ＝２の状態（Ｓｋ（２））からＲＤＳ＝１の状態（Ｓｋ＋１（１））への遷移が可能であることを示している。同様に、行２列１の要素も１であるが、これはＲＤＳ＝１の状態（Ｓｋ（１））からＲＤＳ＝２の状態（Ｓｋ＋１（２））への遷移が可能であることを示している。この遷移行列Ｔからは、隣接する状態にしか遷移できず、例えば、ＲＤＳ＝２からＲＤＳ＝０の直接的な遷移は許されていないことが分かる。本発明の重み系によれば、ペロン・フロベニウスの定理（Perron-Frobenius Theorem）に基づいて数１の式が成り立つことが立証されている。つまり、パスの数を数えて得られる重みの代わりに、次式を解いてて得られるWk(s)を用いて、数え上げ方式の符号化と復号を行うことができることが証明されている。
（数１）
Wk(s) = Ceil{(λmax)N-k・R(s)}
ここで、ｓはＲＤＳの値であり、Wk(s)は時点ｋにおけるｓの関数としての重みを表す。λmaxは、遷移行列Ｔの最大の右固有値であり、定数である。R(s)は、遷移行列Ｔの右固有ベクトルの成分である。Ceilは切り上げ整数化を意味する。
【００５３】
本発明に係る符号化装置は、インデクス算出部１１１、比較出力部１１２、重み算出部１１３と、状態更新部１１５に加え、パラメータ設定部１２１を備え、このパラメータ設定部１２１は、遷移行列生成部１２５、固有ベクトル算出部１２６及び最大固有値算出部１２７を備える。
【００５４】
遷移行列設定部１２５は、トレリス線図におけるそれぞれの状態からの遷移の特性を表す遷移行列Ｔを設定する。図８は、上記第１の実施形態に関する説明で述べたように、Ｍ＝２のＲＤＳ制限コードによって制約条件を付与する場合の遷移行列Ｔを示している。遷移行列Ｔは、その列方向において時点ｋの状態Ｓｋを表し、行方向においてその次の時点ｋ＋１に遷移させる状態Ｓｋ＋１を表している。具体的には、遷移行列Ｔは、状態Ｓｋからの遷移の可否を０又は１の数値によって表している。１は遷移が可能であることを、０は遷移が不可であることを示す。上から第１行目は、ＲＤＳ＝２の状態Ｓｋ（２）から次時点の状態Ｓｋ＋１（ｓ）への遷移の可否を表し、Ｓｋ（２）からＳｋ＋１（１）への遷移のみが可能であり、それ以外のＳｋ＋１（２），Ｓｋ＋１（０），Ｓｋ＋１（−１）及びＳｋ＋１（−２）への遷移は不可であることを示している。同様に、上から第２行目は、ＲＤＳ＝１の状態Ｓｋ（１）から次時点の状態Ｓｋ＋１（ＲＤＳ）への遷移の可否を表し、Ｓｋ（１）からＳｋ＋１（２）及びＳｋ＋１（０）への遷移が可能であり、それ以外のＳｋ＋１（１），Ｓｋ＋１（−１）及びＳｋ＋１（−２）への遷移は不可であることを示している。
【００５５】
固有ベクトル算出部１２６は、遷移行列生成部１２５によって設定した遷移行列Ｔの右固有ベクトルＲを算出する。
【００５６】
最大固有値算出部１２７は、上記設定した遷移行列Ｔの最大の右固有値λを算出する。
【００５７】
重み算出部１１３は、パラメータ設定部１２１によって設定した遷移行列Ｔの固有ベクトルＲ及び最大固有値λを入力し、次式によって状態Ｓｋの重みＷｋ（ｓ）を算出する。次式は、遷移行列Ｔに基づいて導出することができる。
（数２）
Wk(s) = Ceil{(λmax)N-k・R(s)}
【００５８】
遷移行列Ｔは、トレリス線図の構造に基づいて決まるものである。 与えられたトレリス線図に関する遷移行列Ｔについて、１つの最大の右固有値λmax（＝定数）と、状態（例えば、Ｓk（２），Ｓｋ（１），…，Ｓｋ（−２））の数に応じた成分数を有する右固有ベクトルとが求まる。固有ベクトルは、遷移行列から比較的容易に算出できる。通常、固有ベクトルの成分は最大値が１となるように正規化する。固有ベクトルの成分は、それぞれの状態に対応しており、ＲＤＳの値であるｓの関数となっており、この例では取りうるｓの値が５つである（ｓ＝−２〜２の整数）ことに対応して、５つの成分を有する。これをＲ（ｓ）と呼ぶ。 
【００５９】
以上のような、重みの計算方法をフローチャートに整理したものを図７に示す。上述のように遷移行列Ｔが求まる。この遷移行列にペロン・フロベニウスの定理を適用するためには、強連結の状態遷移グラフが必要である。つまり、全ての状態のそれぞれを見ると、ある状態は、必ず前のどこかの状態からつながっており、後のどこかの状態へ出ていけるようになっている必要がある。これを遷移行列の視点から見ると、全部の要素がゼロである行または列がないということになる。したがって、遷移行列を生成する場合には、そのような行または列がないか調べて、もしあれば、そのような行または列を削除すべきである。その上で、上記の数２の式を適用することになる。すなわち、遷移行列Ｔの右固有値のうち最大のものλmaxを得て、さらに右固有ベクトルの成分Ｒ（ｓ）を得る。これらは周知の解法あるいはアルゴリズムにより計算することができる。
【００６０】
ここで、上の数１による重みＷｋ(s)の計算では、まず、遷移行列Ｔが分かっているので、それの最大固有値λmaxと固有ベクトルＲ(s)が分かる。固有ベクトルはその最大ベクトルの大きさを１に正規化したものを用いることができる。算出する必要があるのは、(λmax)N-kである。ところが、回路によってこのような累乗を計算しようとすると、乗算器を多く使うことになって、回路設計が複雑になる。そこで、Ｎ−ｋ＝ｙとした上で、新たな変数ｑとＱを導入して、λmaxｙ＝２（ｙ−Ｑ）・２（−ｒ／ｑ）とする。すると、Ｑも整数であるとすると、ｙ（＝Ｎ−ｋ）はもとより整数であるので、２（ｙ−Ｑ）は、ビットシフトにより簡単に計算できるようになるので、回路で簡単に実現することができる。残りの２（−ｒ／ｑ）については、予め、計算結果をルックアップテーブルにまとめておくことによって演算を省略することができる。 つまり、ｒの値がわかった時点で、ルックアップテーブルを参照して、２（−ｒ／ｑ）の値を求めることができる。
【００６１】
すなわち、次式を満たす整数であるｑを求める。
（数３）
２（−１／ｑ）≦λmax／２   
そして、所与のｙ及び上記ｑについて、次式を満たすＱ及びｒ（整数）を求める。ちなみに、Ｑとｒは時点ｋに依存するが、ｑは依存しないものとする。
（数４）
ｙ＝Ｑ・ｑ＋ｒ  
ここで、０≦ｒ≦ｑ−１である。
そして、λmaxの代わりにλ0＝２・２(-1/q)を用いて上記の重み系を計算することとする。このとき、λmaxとλ0との間の誤差は、小さく、例えば、Ｍ＝８，ｑ＝４５であれば、１０のマイナス５乗のオーダーであることが分かっている。すると、
（数５）
λ0ｙ＝２（ｙ−Ｑ）・２（−ｒ／ｑ） 
ここで、１／２＜２（−ｒ／ｑ）＜１，１＜ｒ＜ｑである。
【００６２】
２（−ｒ／ｑ）は、ｑ個の値をとり得るが、１／２〜１の範囲であることから、予め計算しておいて、ルックアップテーブルでの保存が可能である。数４の式からｒが求まった時点で、このルックアップテーブルを利用して２（−ｒ／ｑ）の値を求めることができる。２（ｙ−Ｑ）は、ビットシフトによって簡単に演算することができるので、(λmax)N-kによく近似している(λ0)N-kを浮動小数点法によって演算することができる。
【００６３】
本実施形態によれば、ある状態遷移行列Ｔに対して、ｑと２（−ｒ／ｑ）を予め求めて記憶しておけば 、λmax を容易に計算することができる。また、固有ベクトルを予め算出して記憶しておくことも容易であるし、また、その記憶も困難を伴うものではない。したがって、状態の遷移のたびに重みＷｋを計算することが可能であるので、状態毎に重みＷｋを記憶しておくための記憶素子の容量を削減できる。換言すれば、数え上げ法において、本発明によって、Ｎ＝４０００といった大きな数値の符号化と復号が実現できるようになっている。
【００６４】
以下、本発明の復号方法の二つの実施形態を説明する。本実施形態では、所定の拘束条件（例えば、Ｍ＝２のＲＤＳ拘束条件）のもとで冗長ビットを含んで設定したコード長Ｎの符号ｃを、ｎビットのもとのデータ(source data)に復号する（図２）。
【００６５】
［左から右への復号］
図９は、本実施形態に係る復号装置の左から右へのアルゴリズム（left-to-right algorithm）の動作を示すフローチャートである。
【００６６】
まず、Ｓ２１では、初期化として、インデクスＩを０に設定するとともに、時点ｋを０に、状態をＳ０（０）に設定する。ＲＤＳの値ｓはゼロである。
【００６７】
Ｓ２２では、入力した符号内の対応する数値ｃ（ｋ＋１）が「１」であるか否かを判定する。「１」である場合は、Ｓ２３へ進み、「１」でない場合は、Ｓ２４へ進む。
【００６８】
Ｓ２３では、状態ＳｋをＲＤＳが増える方向のパスに沿って状態Ｓｋ＋１に遷移させるとともに（ｓはｓ＋１となる。）、ＲＤＳが減る方向のパスに続く状態の重みＷｋ＋１（ｓ−１）を、インデクスＩに加算する。
（数６）
Ｉ＝Ｉ＋Ｗｋ＋１（ｓ−１）  
【００６９】
Ｓ２４では、状態ＳｋをＲＤＳが減る方向のパスに沿って状態Ｓｋ＋１に遷移させる（ｓはｓ−１となる）。インデクスＩは、現時点の値を維持する（Ｉ＝Ｉ）。
【００７０】
Ｓ２５では、時点ｋを１だけ進めるとともに、１を加算したｋが（Ｎ−１）以下であるか否かを判定する。（Ｎ−１）以下である場合は、Ｓ２２へ戻り、（Ｎ−１）よりも大きい場合は、復号処理を終了する。
【００７１】
このように、符号化に際してトレリス線図上で状態Ｓが遷移するパスは、復号する符号内の個々の数値（０または１）に基づいて特定することができる。従って、本実施形態によれば、状態Ｓが遷移するパスに基づいて、符号に対するもとのデータｉの十進法インデクスＩを算出することが可能である。そして、入力データの取りうる値とその十進法インデクスとの関係を予め定めておくことで、インデクスと符号との対応を計算によって判断し、符号をもとのデータに復号することができる。このようなやり方では、インデクスと符号との対応を記憶するためのルックアップテーブルが不要となる。
【００７２】
ここで、この重みの積算について、図４のトレリス線図を参照して、符号ｃ１＝（００１１１００１１１）を入力した場合を例に説明する。入力した符号ｃ１において、最初の二つの数値は０であるので、Ｉ＝０のままである。第３番目の値は１であるがＷ３（−３）の値は上述のようにゼロになるので、Ｉ＝０のままである。第４番目の値も１であり、状態はＳ４（０）となる。この状態Ｓ４（０）を始点としてＲＤＳが減る方向に続くパスの数である重みＷ５（−１）が１８であるので、これを時点４において切り捨てられていたパスの数として積算する。これを次々と行って行くと、Ｉは３５（時点５）、３９（時点８）、４１（時点９）と積算されていき、最終的に時点９までで、Ｉ＝４１ということが分かる。このインデクスが４１であるというは、もとのデータの４２番目の符号であることが分かるので、もとのデータへと復号することができる。
【００７３】
そして、インデクス算出部２１４は、算出した重み積算値をインデクスＩに設定し、もとのデータｉとインデクスＩとの予め定められた関係に基づいて、インデクスＩをもとのデータｉに換算し、出力する。本実施形態において、インデクスＩは、もとのデータｉの十進数換算値であるので、インデクスＩともとのデータｉは直接的に関連している。
【００７４】
以上に述べた第２の実施形態では、符号の先頭から後尾に向けてパスを特定し、ＲＤＳが減る方向のパスに沿って状態を遷移させることによって切り捨てられていたパスの数である重みＷｋ＋１（ｓ−１）を積算することとした。このような方法に限らず、符合の後尾から先頭に向けてパスを特定することによっても復号を実行することができる。このように符号の後尾から先頭に向けてパスを選択する、第３の実施形態に係る復号方法について、以下に説明する。
【００７５】
図１０は、上記の第２の実施形態を実行するための復号装置のブロックダイアグラムである。
【００７６】
状態更新部２１１は、符号ｃを受け付けて、この入力された符号ｃ内の個々の数値０または１に応じてトレリス線図（図４）上で状態が遷移するパスを特定する。重み算出部２１２は、時点ｋにおける状態Ｓｋ（ｓ）の重みＷｋ（ｓ）を算出する。本実施形態において、重み算出部２１２は、トレリス線図上の状態Ｓｋ（ｓ）毎に重みＷｋ（ｓ）を算出する。重み算出部２１２に必要なデータを与えるパラメータ設定部２２１を備え、このパラメータ設定部２２１は、遷移行列生成部２２５、固有ベクトル算出部２２６及び最大固有値算出部２２７を備える。パラメータ設定部２２１は、第１の実施形態に係る符号化装置のパラメータ設定部１２１（図１）と同様の構成であり、第１の実施形態の場合と同様に本発明の装置に必ずしも含まれなくてもいい部分である。
【００７７】
インデクス算出部２１４は、状態更新部２１１によって特定したパスに従って状態を遷移させることによって切り捨てられるパスに続く状態の重みＷｋ＋１（ｓ＋１），Ｗｋ＋１（ｓ−１）を求め、これを時点毎に積算する。ここで、この重みの積算について、図４のトレリス線図を参照して、符号ｃ１＝（００１１１００１１１）を入力した場合を例に説明する。入力した符号ｃ１において、現時点４の状態は、Ｓ４（ｓ）＝Ｓ４（０）である。現時点４に対応する符号ｃ１内の数値が「１」であることから、この状態Ｓ４（０）を始点としてＲＤＳが減る方向に続くパスの数である重みＷ５（−１）＝１８を求め、これを時点４において切り捨てられていたパスの数として積算する。これを次の時点について行って、各時点について算出される切り捨て分の数を積算するのである。
【００７８】
そして、出力部２１５は、算出した重み積算値をインデクスＩに設定し、復号データｉとインデクスＩとの予め定められた関係に基づいて、インデクスＩを復号されたもとのデータｉに換算し、出力する。本実施形態において、インデクスＩは、もとのデータｉの十進数換算値であるので、インデクスＩともとのデータｉは直接的に関連している。なお、上述のように、ここでは、インデクスを十進表示にしているが、これは説明のためであり、実際の計算においては、２進法の数値のままであって良いので、出力部２１５を省略することも可能である。
【００７９】
本実施形態では、重み積算値の算出において、負方向のパスを選択することによって切り捨てられるパスの数を積算したことから、算出した重み積算値をインデクスＩに代入することができる。換言すれば、本実施形態において算出される重み積算値は、インデクスＩに等しい。しかしながら、正方向のパスを選択することによって切り捨てられるパスの数を積算することによってもインデクスＩを算出することが可能である。その場合は、時点０における状態の重みＷ０から重み積算値を減算したものをインデクスＩとして、もとのデータｉに変換する。
【００８０】
［右から左への復号］
図１１は、本発明の第３の実施形態に係る右から左への復号アルゴリズムの各ステップを示すフローチャートである。まず、最も右側の最終時点における状態Ｓｆを求める必要がある。この状態Ｓｆは符号から決定することができる。例えば、符号がｃ＝（ｃ（１）ｃ（２）ｃ（３）．．．ｃ（ｆ））であれば、それぞれの符号値の１に＋１を、０に−１を対応させて、和を取ることにより、ＲＤＳを計算することができる。符号値ｃ（１）からｃ（ｆ）に対応する＋１と−１の和を取ることによりＳｆでのＲＤＳの値をすることができ、これを最終状態におけるｓの値とする（ステップＳ３０）。Ｓ３１では、初期化として、インデクスＩを０に設定するとともに、時点ｋをＮに、最終時点の状態を求めたＳｆに設定する。
【００８１】
Ｓ３２では、ｃ（ｋ）の値から、現時点ｋの状態Ｓｋ（ｓ）が一つ前の時点のどの状態Ｓｋ−１（ｓ’）から遷移したのかを判定する。
【００８２】
Ｓ３３では、入力された符号内の対応する数値ｃ（ｋ）が１であるか否かを判定する。１である場合は、Ｓ３４へ進み、１でない場合は、Ｓ３５へ進む。
【００８３】
Ｓ３４では、状態ｓを一つ前の時点の状態ｓ’に遷移させるとともに、ｓ’からｓに状態を遷移させることによって切り捨てられるパスの数である重みＷｋ（ｓ’−１）を、インデクスＩに加算する。
（数７）
Ｉ＝Ｉ＋Ｗｋ（ｓ’−１）  
【００８４】
Ｓ３５では、状態ｓを前の時点の状態ｓ’に遷移させる。インデクスＩは、現時点の値を維持する（Ｉ＝Ｉ）。
【００８５】
Ｓ３６では、時点ｋを１つ前に戻すとともに、１を減算したｋが１以上であるか否かを判定する。１以上である場合は、Ｓ３３へ戻り、１よりも小さい場合は、データｉに関する復号処理を終了する。
【００８６】
本実施形態によれば、重みＷｋを計算によって設定することが可能であるとともに、符号への変換に際して算出した最大固有値λ等の演算結果を再利用して復号を実行することができるので、回路構成の簡略化が可能である。また、上記の左から右への復号アルゴリズムの場合、Ｉ＝Ｉ＋Ｗｋ＋１（ｓ−１）計算する際、時点k=0の時Ｗｋ＋１の値は(λmax)N-k  によって非常に大きいので、ハードウエアのサイズが大きくなる。右から左への復号アルゴリズムによれば、ハードウエアのサイズを抑えることができる利点がある。
【００８７】
なお、本発明によれば、もう一つの実施形態として、符号化と復号の際に、処理速度を上げるため、入力信号を並列化し、時点kから時点k+1に遷移するときにmビット(m>1)を同時に符号化または復号することも可能である（これをhigh-radixという）。この場合には、それに合わせて遷移行列Ｔの形は変わるが、符号化または復号の方法自体は変わらない。
【符号の説明】
【００８８】
１１１…インデクス算出部、１１２…比較・出力部、１１３…重み算出部、１１５…状態更新部、１２１…パラメータ設定部、１２５…遷移行列生成部、１２６…固有ベクトル算出部、１２７…最大固有値算出部、２１１…状態更新部、２１２…重み算出部、２１３…重み記憶部、２１４…インデクス算出部、２１５…出力部、２２１…パラメータ設定部、２２５…遷移行列生成部、２２６…固有ベクトル算出部、２２７…最大固有値算出部 。 
【図１】
0005409196.tif 000002
【図２】
0005409196.tif 000003
【図３】
0005409196.tif 000004
【図４】
0005409196.tif 000005
【図５ａ】
0005409196.tif 000006
【図５ｂ】
0005409196.tif 000007
【図５ｃ】
0005409196.tif 000008
【図６】
0005409196.tif 000009
【図７】
0005409196.tif 000010
【図８】
0005409196.tif 000011
【図９】
0005409196.tif 000012
【図１０】
0005409196.tif 000013
【図１１】
0005409196.tif 000014