(57)【特許請求の範囲】
【請求項１】
それぞれが１つの発生確率を有する複数の文字を含むメッセージを符号化する方法であって、
前記複数の文字（Ｘ）を含む１つのメッセージを受けるステップと、
２進コード化メッセージ（Ｈ、Ｙ、Ｅ、Ｃ）を発生するため、それぞれが複数の２進値ディジットを有する複数のコード語（Ｈ）を前記文字（Ｘ）に割り当てることによって受信メッセージをコード化するステップと、
を具備しており、
前記コード語（Ｈ）が、前記文字（Ｘ）の発生確率と前記コード語（Ｈ）内の第１の値（「１」）を有するビットの数とにほぼ従って前記文字（Ｘ）に割り当てられ、より高い発生確率の文字（Ｘ）には、より低い発生確率の文字（Ｘ）に割り当てられるものよりも第１の値（「１」）を有するビットが少ないコード語（Ｈ）が割り当てられるようにする符号化方法において、この符号化方法が、
相互に異なった文字（Ｘ）の数をカウントしたカウント値に基づいて量子化信号レベルの数（ｒ）を決定するステップと、
前記量子化信号レベルの数（ｒ）に基づいて、コード語（Ｈ、Ｙ）内のビットの数（ｄ）を最小化あるいは減少するように選択するステップと、を含むことを特徴とする符号化方法。
【請求項２】
請求項１記載の符号化方法において、コード化メッセージ（Ｅ、Ｃ）内のビットの数を更に減少するように２進コード化メッセージを圧縮すること（Ｓ１４０、Ｓ１５０）、を更に含むことを特徴とする符号化方法。
【請求項３】
請求項１または２記載の符号化方法において、
受信メッセージ内の文字の発生確率とコード語内の第１の値（「１」）を有するビットの数とに基づいて文字およびコード語間の索引リストを発生し、より高い発生確率の文字にはより低い発生確率の文字に割り当てられるものよりも第１の値（「１」）を有するビットが少ないコード語が割り当てられるようにするステップと、
前記リストに従って前記コード語（Ｈ）を前記文字（Ｘ）に割り当てることによって受信メッセージをコード化するステップと、を更に含むことを特徴とする符号化方法。
【請求項４】
請求項３記載の符号化方法において、伝送を指示する信号と共に前記リストを伝送すること、を更に含むことを特徴とする符号化方法。
【請求項５】
請求項３または４記載の符号化方法において、現在の索引リストの基準となった相対発生頻度から、受信メッセージ内の文字の相対発生頻度がほぼ外れたときに、文字およびコード語間の新たな索引リストを定めること、を更に含むことを特徴とする符号化方法。
【請求項６】
請求項１〜５のいずれか１項記載の符号化方法において、
前記符号化ステップが、
前記複数の文字に対して、前記少なくとも１つのメッセージ内の文字の相対頻度を指示する値（ｐ）を計算するステップ（Ｓ４０）と、
複数の２進ディジットからなる第１の２進コード化コードシンボル（Ｈ１）を、最も高い相対頻度（ｐ１）を有する文字に割り当てるステップ（Ｓ６０）と、
前記第１の２進コード化コードシンボル（Ｈ１）内の全てあるいはほぼ全ての２進ディジットを第２の２進値（「０」）に設定するステップと、
同じ相対頻度（ｐ１、ｐ２）を有する２つのシンボル（Ｈ１、Ｈ２）間でまたは近似相対頻度を有する２つのシンボル間内でハミング重みの差が最小となるように特異なシンボル（Ｈ２、Ｈ３）を各特異な残りの文字に割り当てるステップと、を具備する方法に従って行なわれることを特徴とする符号化方法。
【請求項７】
請求項３〜６のいずれか１項記載の符号化方法において、複数の受信メッセージが索引リストのための基準を形成するようにし、前記複数の受信メッセージ内の文字がコード語の語長の基準となる相互に異なった文字の前記カウント値を構成することを特徴とする符号化方法。
【請求項８】
請求項３〜７のいずれか１項記載の符号化方法において、受信メッセージが現在の索引リストよりもより大きな数の相互に異なった文字を含むときに、前記文字（Ｘ）および前記コード語（Ｈ）間の新たな索引リストを定めること、を更に含むことを特徴とする符号化方法。
【請求項９】
請求項１〜８のいずれか１項記載の符号化方法において、それぞれが第１の値または第２の値を有する第１の組（Ｙ）の２進ディジットとして前記コード語（Ｈ）を逐次的に与えること、を更に含むことを特徴とする符号化方法。
【請求項１０】
不均一確率密度を有する振幅を持ったアナログ信号を符号化する方法において、
複数の信号レベル範囲の１つの中にあるものとして信号を量子化するステップと、
２進コード化メッセージ（Ｈ、Ｙ、Ｅ、Ｃ）を発生するために、それぞれが複数の２進値ディジットを有するコード語（Ｈ）を前記量子化された信号に割り当てることによって前記量子化された信号をコード化するステップと、を含んでおり、
前記コード語（Ｈ）が量子化レベルの発生確率と前記コード語内の第１の値（「１」）を有するビットの数とに従って量子化レベルに割り当てられ、より高い発生確率の量子化レベルにはより低い発生確率の量子化レベルに割り当てられるものよりも第１の値（「１」）を有するビットが少ないコード語が割り当てられるようにする符号化方法において、この符号化方法が、
履歴最大振幅と選択された振幅分解能とに基づいて量子化信号レベルの数（ｒ）を決定するステップと、
コード語（Ｈ、Ｙ）内のビットの数（ｄ）を最小化もしくは減少するように決定された前記量子化信号レベルの数（ｒ）に応じてコード語にとって好ましい前記ビットの数（ｄ）を選択するステップと、を含むことを特徴とする符号化方法。
【請求項１１】
請求項１０記載の符号化方法において、コード化メッセージ（Ｅ、Ｃ）内のビットの数を更に減少するように２進コード化メッセージを圧縮すること（Ｓ１４０、Ｓ１５０）、を更に含むことを特徴とする符号化方法。
【請求項１２】
請求項１０または１１記載の符号化方法において、量子化信号範囲およびコード語間の索引リストを発生することを更に含んでおり、前記リストが受信アナログ信号の量子化信号範囲の発生確率とコード語内の第１の値（「１」）を有するビットの数に基づきより高い発生確率の量子化信号範囲にはより低い発生確率の量子化信号範囲に割り当てられるものよりも第１の値（「１」）を有するビットが少ないコード語が割り当てられるようになっており、前記リストに従って前記コード語（Ｈ）を量子化信号範囲に割り当てることによって受信アナログ信号をコード化することを更に含むことを特徴とする符号化方法。
【請求項１３】
請求項１２記載の符号化方法において、伝送を指示する信号と共に前記リストを伝送すること、を更に含むことを特徴とする符号化方法。
【請求項１４】
請求項１２または１３記載の符号化方法において、現在の索引リストの基準となった相対発生頻度から、受信アナログ信号の量子化信号範囲の相対発生頻度がほぼ外れたときに、量子化信号範囲およびコード語間の新たな索引リストを定めること、を更に含むことを特徴とする符号化方法。
【請求項１５】
請求項１０〜１４のいずれか１項記載の符号化方法において、
前記符号化ステップが、
少なくとも１つの所定の時間間隔の間にアナログ信号を受けるステップと、
複数の量子化振幅レベル範囲を決定するステップと、各振幅レベル範囲に対して、前記アナログ信号の振幅レベル範囲の相対頻度を指示する値（ｐ）を計算するステップと、
複数の２進ディジットからなる第１の２進コード化コードシンボル（Ｈ１）を、最も高い相対頻度（ｐ１）を有する振幅レベル範囲に割り当て（Ｓ６０）、前記第１の２進コード化コードシンボル（Ｈ１）内の全てまたは実質的に全ての２進ディジットを第２の２進レベル（「０」）に設定するステップと、
同じ相対頻度（ｐ１、ｐ２）を有する２つのシンボル間でまたは近似相対頻度を有する２つのシンボル間内でハミング重みの差が最小となるように特異なシンボル（Ｈ２、Ｈ３）を各残りの振幅レベル範囲に割り当てるステップと、を具備する方法に従って行なわれることを特徴とする符号化方法。
【請求項１６】
請求項１０〜１５のいずれか１項記載の符号化方法において、量子化信号レベルの数（ｒ）を表す語を供給すること、を更に含むことを特徴とする符号化方法。
【請求項１７】
請求項１０〜１６のいずれか１項記載の符号化方法において、履歴最大振幅を表す語を供給すること、を更に含むことを特徴とする符号化方法。
【請求項１８】
請求項１２〜１７のいずれか１項記載の符号化方法において、現在の索引リストの基準となった最大振幅よりもより大きな最大振幅を受信信号が有する時に量子化信号範囲および前記コード語（Ｈ）間の新たな索引リストを定めること、を更に含むことを特徴とする符号化方法。
【請求項１９】
請求項１０〜１８のいずれか１項記載の符号化方法において、それぞれが第１の値または第２の値を有する第１の組（Ｙ）の２進ディジットとして前記コード語（Ｈ）を逐次的に与えること、を更に含むことを特徴とする符号化方法。
【請求項２０】
請求項９または１９記載の符号化方法において、
第１の組のディジット（Ｙ）を符号化して（Ｓ２２０〜Ｓ３７０、図３Ｂ、３Ｃ）、第２の組（Ｅ）の２進ディジット（ｅｉ、ｅｉ＋１）を発生するステップをさらに含み、
前記２進ディジットを発生するステップは、第２の組（Ｅ）内の第２の２進値を有するディジットの数が第１の組（Ｙ）内の第２の２進値を有するディジットの数よりも大きくなるように第２の組（Ｅ）のディジット（ｅｉ、ｅｉ＋１）を選択することを特徴とする符号化方法。
【請求項２１】
請求項２０記載の符号化方法において、第２の組（Ｅ）の２進ディジットのディジット（ｅｉ）を発生する前記ステップは、
第２の組（Ｅ）の最初からｍ（正の整数）までのディジット（ｅｉ）の値を、第１の組（Ｙ）の最初からｍ（正の整数）までのディジット（ｙｉ）の値に等しく設定するステップを含むことを特徴とする符号化方法。
【請求項２２】
請求項２０または２１記載の符号化方法において、第２の組（Ｅ）の２進ディジットの次のディジット（ｅｉ＋１）を発生する前記ステップは、
第１の組のディジット（Ｙ）の多数の前のディジット（ｙｉ）に応じて予測値（ｐｉ＋１）を発生するステップと、
第１の組のディジット（Ｙ）での実際のディジット（ｙｉ＋１）の値を読み出すステップと、
予測値（ｐｉ＋１）および実際のディジット（ｙｉ＋１）の値間のハミング距離を計算する（Ｓ３００）ステップと、
第２の組のディジット（Ｅ）でのディジット（ｅｉ＋１）の値を計算されたハミング距離値に等しく設定するステップと、を含むことを特徴とする符号化方法。
【請求項２３】
請求項２０記載の符号化方法において、前期第２の組（Ｅ）の２進ディジットのディジット（ｅｉ）を発生する前記ステップは、
第２の組（Ｅ）の最初からｍ（正の整数）までのディジット（ｅｉ）の値を第１の組（Ｙ）の最初からｍ（正の整数）までのディジット（ｙｉ）に値に等しく設定するステップと、
第１の組のディジット（Ｙ）での所定数（ｍに等しいかまたはｍよりも小さい正の整数）の前のディジット（ｙｉ）に応じて予測値（ｐｉ＋１）を発生するステップと、
第１の組のディジット（Ｙ）の実際のディジット（ｙｉ＋１）の値を読み出すステップと、
予測値（ｐｉ＋１）および実際のディジット（ｙｉ＋１）の値間のハミング距離を計算する（Ｓ３００）ステップと、
第２の組のディジット（Ｅ）のディジット（ｅｉ＋１）の値を計算されたハミング距離値に等しく設定するステップと、を含むことを特徴とする符号化方法。
【請求項２４】
請求項２２または２３記載の符号化方法において、予測値（ｐｉ＋１）を発生する前記ステップは、
第１の組のディジット（Ｙ）でのディジットに応じてそれぞれが選択可能である（Ｓ２２４９、Ｓ３５０）複数の予測器カウント値（Ｖ）を定めるステップ（Ｓ２３０）と、
全ての予測器カウント値（Ｖ）を０に初期設定するステップと、
その後に、第１の組のディジットでのディジット（ｙ１〜ｙｍ）の組合せを選択するステップと、
ｆ１）第１の組のディジット（Ｙ）でのディジットの選択された組合せに応じて予測器カウント値（Ｖ）を選択するステップと、
ｆ２）選択された予測カウント値（Ｖ）を読み出すステップと、
ｆ３）選択された予測器カウント値（Ｖ）が所定値よりも大きければ予測値（ｐｉ＋１）を第１の値に設定し（Ｓ２６０、Ｓ２７０）、選択された予測器カウント値（Ｖ）が前記所定値よりも小さければ予測値（ｐｉ＋１）を第２の値に設定する（Ｓ２６０、Ｓ２８０）ステップと、
ｆ４）第１の組のディジット（Ｙ）での実際のディジット（ｙｉ＋１）の値が１に等しければ（Ｓ３１０）選択された予測器カウント値（Ｖ）を増加し（Ｓ３２０）、第１の組のディジット（Ｙ）での実際のディジット（ｙｉ＋１）の値が０に等しければ（Ｓ３１０）選択された予測器カウント値（Ｖ）を減少する（Ｓ３３０）ステップと、
ｆ５）第１の組のディジット（Ｙ）のディジットでの新たな組合せを選択するステップと、
第１の組のディジット（Ｙ）での全てのディジット（ｙｉ＋１）が読み出されるまでステップｆ１）からｆ５）を繰り返すステップと、を含むことを特徴とする符号化方法。
【請求項２５】
請求項２２から２４のいずれか１項記載の符号化方法において、予測値（ｐｉ＋１）および実際のディジット（ｙｉ＋１）間のハミング距離を計算する（Ｓ３００）前記ステップが、予測直（ｐｉ＋１）と、実際のディジット（ｙｉ＋１）のモジュロ２の値とを加算するステップ（Ｓ３００）を含むことを特徴とする符号化方法。
【請求項２６】
請求項１から２５のいずれか１項記載の方法において、符号化メッセージを圧縮するステップを更に含むことを特徴とする方法。
【請求項２７】
請求項１から２５のいずれか１項記載の方法において、第２の組のディジット（Ｅ）をハフマンコード化に従って符号化するステップを更に含むことを特徴とする方法。
【発明の詳細な説明】
発明の技術分野
本発明は情報を符号化する方法並びに情報を復号する方法に関する。また、本発明は情報を符号化する装置並びに情報を復号する装置に関する。
関連技術の説明
情報の処理において、ある場合に、情報を担っているメッセージを変換してそのメッセージのシンボルを特定の目的に適合させるようにすることが望まれる。メッセージを変換する概念は、往々、符号化あるいは復号と呼ばれている。普通、情報を処理する電子装置は情報を記憶するメモリユニットとこのメモリユニットから取り出した後に前記情報を表示するディスプレイユニットとを共通に備えている。メモリユニットの記憶可能な情報量を最大化する目的のためおよび／またはメモリユニットのサイズを減少する目的のため、情報は圧縮された状態でメモリユニットに記憶されることができる。
米国特許第５，０６２，１５２号はある振幅範囲を有するアナログ信号を不均一確率密度で処理する方法に関連する。この方法はこのアナログ信号を複数の信号レベルの１つの中に入るものとして量子化すること、並びに量子化レベルの発生確率に従って２進コード語を量子化レベルに割り当てることを含んでいる。米国特許第５，０６２，１５２号に記載されている方法によれば、各コード語は８つの２進値ディジットを含むように予め決定されている。
米国特許第５，４８８，６１６号は符号化方法に関連する。米国特許第５，４８８，６１６号によれば、それぞれが一つの発生確率を有するシンボルが設けられる。第１の方法ステップは各シンボルの発生確率に従って各シンボルに可変長コード語を割り当てることである。このステップはハフマンコード化を用いる。その後、可変長コード語は第１のコードＣ32および第２のコードＣ34を与えるように２つの異なった態様でコード化される。最後のステップにおいて、コードＣ32、Ｃ34の一方または両方が可逆可変長コードを与えるように選択される。
概要
本発明が取り組む１つの問題点は不均一確率密度を有するエンティティからなるメッセージを符号化してそのメッセージを例えば無線リンクで伝送する時に最少の帯域幅と最少の電力で済むようにする方法を提供することである。
この問題点はメッセージを符号化する方法によって対処される。このメッセージはそれぞれが１つの発生確率を有する複数のエンティティを具備する。本発明の一実施例によれば、各エンティティは１つの文字であり、この方法は、
１つのメッセージを受けるステップと、
それぞれが複数の２進値ディジットを有するコード語（Ｈ）を受信文字（Ｘ）に割り当てることによって受信メッセージをコード化して２進コード化メッセージを発生するステップと、
を具備しており、前記コード語は前記文字の発生確率とコード語（Ｈ）内の第１の値（１）を有するビットの数とに実質的に従って文字（Ｘ）に割り当てられてより高い発生確率の文字にはより低い発生確率の文字に割り当てられるものよりも第１の値（１）を有するより少ないビットを持ったコード語が割り当てられるようにする。このコード化方法はコード化メッセージ内のビットの数を最小にするように２進コード化メッセージを発生することを付加的に含んでいる。
一実施例によれば、コード化メッセージ内のビットの数は、
履歴最大数の相互に異なった文字に基づいて数を決定することと、
相互に異なった文字の決定された数に応じてコード語にとって好ましい語長を選択することと、
によって最小化される。
符号化されるべきメッセージが不均一確率密度を有するアナログ信号の形態である場合には、このアナログ信号の種々の量子化レベルは各エンティティが１つの発生確率を有するようなエンティティを構成する。本発明の一実施例によれば、この方法は、
複数の信号レベル範囲の１つの中にあるものとして信号を量子化すること、並びに
それぞれが複数の２進値ディジットを有するコード語を量子化レベルに割り当てることによって被量子化信号をコード化して２進コード化メッセージを発生すること、
を含んでおり、前記コード語は量子化レベルの発生確率と前記コード語内の第１の値（「１」）を有するビットの数とに従って量子化レベルに割り当てられてより高い発生確率の量子化レベルにはより低い発生確率の量子化レベルに割り当てられるものよりも第１の値（「１」）を有するより少ないビットを持ったコード語が割り当てられるようにする。このコード化方法はコード化メッセージ内のビットの数を最小とするように２進コード化メッセージを発生することを付加的に含んでいる。
一実施例によれば、コード化メッセージ内のビットの数は、
履歴最大振幅および選択された振幅分解能に基づいて量子化信号レベルの数を決定すること、並びに
量子化信号レベルの決定された数に応じてコード語にとって好ましい語長を選択すること、
によって最小化される。
本発明の他の実施例によれば、コード化メッセージのビット内の数はコード化メッセージを圧縮することによって最小化される。一実施例によれば、これはハフマンコード化に従って２進コード化メッセージを符号化することによって達成される。
好適実施例によれば、２進コード化メッセージは第１のビットストリームＹとして解釈され、このビットストリームはある推定プロセスを受け、それによって第２のビットストリームＥが発生される。この推定プロセスの結果第２のビットストリームＥ内の値０を有するビットの割合は第１のビットストリームＹの場合よりも大きくなる。更に、第２のビットストリームＥでのビットのシーケンスはメモリなしのベルヌーイソースの出力と類似する。値１を有するビットの数が極めて小さくかつ第２のビットストリームＥでのビットのシーケンスがメモリなしのベルヌーイソースの出力に類似しているため、ハフマンコード化の成功の条件は第２のビットストリームＥにおいて最適にされる。好適実施例によれば、第２のビットストリームＥはハフマンコード化に従って符号化される。
この方法はメッセージの情報内容を伝送するために必要なビットの数を最小化し、それによって伝送時間並びに伝送のために必要な電力を最少化した状態で帯域幅要求を減少する長所を有している。
【図面の簡単な説明】
本発明の簡単な理解のため、それは一例として以下の添付図面に関連して説明される。
図１Ａは人間の言語メッセージの文字とコードシンボルとの間の対応表を作成する方法を示すフローチャートである。
図１Ｂは変換表を表すものである。
図２は本発明の一実施例によるデータ圧縮の方法を示すフローチャートである。
図３Ａは本発明の一実施例による１組の有限状態マシンを示す。
図３Ｂおよび３Ｃは図２によるフローチャート内の１つのステップの詳細を示すフローチャートである。
図３Ｄは図３Ａによる有限状態マシンと共に作用する変換表の例である。
図３Ｅはビットストリームの例である。
図４は本発明の一実施例によるデータ圧縮装置の第１の実施例の概略ブロック図を示す。
図５は図４によるデータ圧縮装置において使用する推定器の概略ブロック図である。
図６は図２に関連して説明される方法に従って圧縮されて記憶された情報を復元する手段を備えた携帯電子装置の概略ブロック図である。
図７は本発明の一実施例によるデータ復元装置を示す。
図８は本発明の１つの実施例による復号する方法を示すフローチャートである。
図９Ａおよび９Ｂは図８によるフローチャートのステップの１つの詳細を示すフローチャートである。
図１０はアナログ信号をコード化しかつ復号するユニットを含んだ通信システムの概略ブロック図である。
実施例の詳細な説明
人間の言語はある数の語（ワード）からなり、これら語のあるものは他のものよりもより頻繁に使用される。各語は文字の特定の組合せによって、時によってはただ１つの文字によって表され得る。これはある文字が任意の特定の言語において他のものよりもより頻繁に使用されることを意味する。移動電話機のような電子装置においては、ある数の所定のメッセージが記憶されており、そのそれぞれをある事象に応じて移動電話機のディスプレイユニットに表示させるようにしている。普通、これらのメッセージは読出し専用メモリに記憶されている。あるメッセージを表示するために、対応するデータがメモリから読み出され、各文字に対して対応するＡＳＣＩＩコードがディスプレイユニットに供給され、これはそれに対応して選択されたメッセージを構成するＡＳＣＩＩの組合せを表示する。
上で述べたように、ある文字は１つの特定の人間言語においてあるいは１つの特定の所定の組のメッセージにおいて他の文字よりもより高い相対頻度を有している。本発明は所定の言語で情報を表すために必要なビットの数を減少しおよび／または任意の言語で所定の組のメッセージを表すために必要なビットの数を減少する方法に関する。
変換表を作成する方法
図１Ａは選ばれた組のメッセージ中の文字または選択された言語内の文字が選択された形式のメッセージの全ハミング重みを最小化するようにコードシンボルに変換されることができるようにする変換表を得る方法を示すフローチャートである。
１つのシンボルは１つあるいは複数の要素からなることができる。好適実施例によれば、各コードシンボルは２進ディジットの組合せである。
値１を有するディジットの数が最小化される時にはハミング重みが最小化される。全ての文字を対応するハミングシンボルに変換することによって、２つの目的が達成される。第１の目的はある重みを各文字に割り当てることである。下で説明されるように、より低いハミング重みはまたシンボルのより大きな圧縮性を与えることになり、これによりハミング重みとシンボルを記憶するために必要なメモリ空間との間につながりを与えることになる。第２に、下で説明する態様でのハミングシンボルへの変換はメッセージの２つの連続文字間の重み差を減少させる。換言すれば、第２のシンボルにおいて第１のシンボルに較べて異なっているディジット位置の数は減少される。
図１Ａに関して、第１のステップＳ１０は人間言語を選択することである。選択された人間言語は、例えば英語、フランス語、スウェーデン語、あるいはメッセージを構成するための文字を使用する任意の他の人間言語となることができる。変数が選択された言語の名称に割り当てられ、この言語識別変数は作成されるべき表を識別するためにセーブされる。
ステップＳ２０において、完全な組のメッセージが受けられる。完全な組のメッセージ中の文字の数は例えば２５００になることができる。本発明の一実施例によれば各文字は８ビットで構成される。
ステップＳ３０において、相互に異なった文字の数がカウントされ、変数がカウント値に割り当てられる。典型的なアルファベットにおいて、相互に異なった文字の数は例えば６４であってもよい。
ステップＳ４０において、各文字の相対頻度が計算され、ステップＳ５０において、これら文字は相対頻度が低下する順に分類される。換言すれば、最も共通に使用される文字はリストの最初に置かれ、最も頻度が小さい文字はリストの最後に置かれる。このようなリストの一例が図１Ｂに示されている。図１Ｂには複数のメモリ位置２０を有するメモリユニット１０が示されている。各メモリ位置は例えば８ビットからなってもよい。第１のメモリ位置は言語識別変数を設けており、これは、例えばリスト／表が英語の１組の言語メッセージで使用される文字からなることを識別する英字Ｅであってもよい。リストの第２のメモリ位置はこの特定のリストに記憶されている文字の数を表す。この例において、異なった文字の数は６４である。第３のメモリ位置は最も高い相対頻度ｐ1を有する文字のためのＡＳＣＩＩコードを含んでいる。この例において、最大頻度文字はＨである。第４のメモリ位置には２番目に高い相対頻度ｐ2を有する文字（この例ではＧ）が記憶されている。この態様で、６４の異なった文字がリストに置かれ、その際に最も低い相対頻度ｐ64を有する文字がリストの最後の位置に置かれる。
ステップＳ６０において、０のみを有するシンボルが最も高い相対頻度ｐ1を有する文字に割り当てられる。図１Ｂに示される例において、選択された組のメッセージが６４の異なった文字だけを含み、従って第１の文字に割り当てられるべきシンボルは全てが０である６つのディジットからなるシンボルとなる。本発明によれば、増加するハミング重みのシンボル（本明細書では、ハミングシンボルという）のリストが作成される。ハミングシンボルは、最も高い相対頻度ｐ1を有する文字が最も低いハミング重みを有するハミングシンボルを割り当てられるようにリスト内の文字に割り当てられる。最も低い相対頻度ｐ64を有する文字にはどの他のハミングシンボルよりも低くないハミング重みを有するハミングシンボルが割り当てられる。しかしながら、第１のハミングシンボルが全てが０である６つのディジットを持つシンボルであるという知識を持ってすれば、重みが概して１重みステップ高い次のハミングシンボルを計算することは可能である。従って、本発明によれば、ハミングシンボルの完全なリストを実際に記憶する必要はない。そうしなくとも、ハミングシンボルにどの位多くのディジットが存在するかを識別すれば十分である。ハミングシンボル内の必要なデイジットの数は文字の数の知識を持てば計算可能であるため、０だけを含む第１のハミングシンボルから出発する引続くハミングシンボルを計算する所定の態様を持つことのみが必要である。
ステップＳ７０において、対応表が作成され、この表は下で説明するように記憶のためのメモリユニットに供給される。実際にはどのハミングシンボルも記憶される必要はないため、対応表はリストの名称を表す変数、リスト内の文字の数を表す数字および減少する相対頻度順の文字を含むことのみ必要である。この最少量の情報を使用すれば、各文字に割り当てられるべき各ハミングシンボルの値を計算することが可能となり、これは対応表を作成するために必要な唯一の情報である。従って、文字のリストおよび制御語（文字の数を表す数字）を記憶することのみ必要であるため、対応表のためには極めて少量のメモリ空間で済むことになる。
メッセージを変換する方法
図２はビットストリームが最小数のディジットを持つようにメッセージをビットストリームに変換する方法を示すフローチャートである。
この方法の実施例の第１のステップＳ１００によれば、複数の文字ＸからなるメッセージＭLはビットストリームＹに変換される。これはメッセージＭLを受け（ステップＳ１１０）、図１Ｂおよび１Ａに関連して上で説明したような表を用いて各文字Ｘを対応するシンボルＨに変換することによって達成される。ステップＳ１２０によれば、メッセージの連続する文字はシンボルＨのストリームが与えられるようにシンボルに連続的に変換される。この方法の次のステップＳ１３０によれば、発生されたシンボルＨはビットストリームとして供給される。
ステップＳ１４０によれば、ビットストリームＹは受信ビットストリームを第２のビットストリームＥに変換する推定器に与えられる。ステップＳ１４０の目的はステップＳ１３０によって作られたビットストリームに応じて殆ど０からなる第２のビットストリームＥを与えることである。ステップＳ１４０の他の目的は独立的にかつ恒等的に分散される確率変数に可及的に近接するディジットの第２のビットストリームＥを与えることである。ステップ１４０は図３に関連して下でより詳細に説明される。
ステップＳ１５０によれば、ステップＳ１４０において作られた第２のビットストリームは圧縮アルゴリズムに従って圧縮される。本発明の一実施例によれば、使用される圧縮アルゴリズムはハフマンコード化である。ハフマンコード化についての詳細な情報のため、Ｄ．Ａ．Ｈｕｆｆｍａｎ著「最少冗長コードの構築方法（Ａ  ｍｅｔｈｏｄ  ｆｏｒ  ｃｏｎｓｔｒｕｃｔｉｏｎ  ｏｆ  ｍｉｎｉｍｕｍ  ｒｅｄｕｎｄａｎｃｙ  ｃｏｄｅｓ）」Ｐｒｏｃ．ＩＲＥ，４０：１０９８−１１０１，１９５２を参照されたい。
圧縮ステップＳ１５０は第２のビットストリームよりも少ないディジットを有する第３のビットストリームＣを発生する。実際、上で説明したような方法は英語のメッセージＭEを元の数のビットの僅か５７．８％までに減少する。この数字は、英語の元のメッセージが２３２３バイトのサイズを必要とした場合に、セルラ電話用の完全な組の状態メッセージに対して達成された。０．５７８の圧縮率は文字を対応するハミングシンボルに変換するために使用される変換表を含んでいる。これは、変換表がメッセージを取り出すべき受信端末で利用可能であると想定してメッセージの実際の圧縮率が一層良好になることを意味する。
ステップＳ１６０によれば、ステップＳ１５０によって発生された第３のビットストリームはメモリ装置に記憶される。別態様として、ステップＳ１５０で与えられた第３のビットストリームはそれを他の電子装置に伝送するための出力に伝送される。
本発明によれば、有利な圧縮比が前記態様で達成される。従って、上の情報変換方法は、被変換メッセージが元のメッセージよりも実質的に少ないメモリ空間しか必要としないために、メッセージをメモリ装置に記憶する前にメッセージを圧縮ビットストリームに変換するのに適している。下の表において、１１の異なった言語のテキストメッセージとメッセージを圧縮した時に達成される対応する圧縮率との例が与えられる。この圧縮比は圧縮メッセージのサイズと変換表のサイズの和を元の組のメッセージのサイズで割ったものとして計算される。
0003995106.tif 000002
上の例（表１参照）から明らかなように、圧縮比は元のメッセージにおいて使用された言語とはほぼ完全に独立している。
ステップＳ１４０は図３Ａ、３Ｂおよび３Ｃに関連してより詳細に説明される。図３Ｂおよび３Ｃに関連して説明される方法は１組の有限状態マシンを使用するため、このような１組の有限状態マシンの一例が図３Ａに示される。本発明の好適実施例に従ったステップＳ１４０による方法を実行する目的のため、ｋ・２mの異なった状態を有する１組の有限状態マシンが使用される。
１つの好適実施例によれば、パラメータｋおよびｍは次のようにして、すなわちｋ＝６およびｍ＝１０のように選択される。この好適実施例によりコード化されるべきメッセージにおいて通常使用されるアルファベットでは２6を越える文字はないためにパラメータｋは６に選ばれる。パラメータｍは、「履歴」を与えるために十分に大きくかつ各状態において不完全な統計値に関連した統計値に関連した問題を回避する上で十分に小さく選択される。パラメータｍの選択のための他の配慮は図５および３Ｃに関連して下に説明するようにカウント値Ｖを生じさせるカウンタ用のメモリの可用性に応じてそれを好ましい値に選択することである。
この方法の根底の原理を示す目的のため、３つの２2の状態しか持たない１組の有限状態マシンが図３Ａに示されている。このため、図３Ａに示されるこの組の有限状態マシンはｋ＝３およびｍ＝２に基づいている。ｍ＝２は各状態が図３Ａに示されるように２つのディジットによって定められることを意味している。図３Ａのこの組の有限状態マシンはｋが３に等しいため３つの異なった有限状態マシン１１０、１２０および１３０で構成される。図３Ａに示される円のそれぞれは有限状態マシン１１０、１２０および１３０の組の状態を表し、また本発明によりカウント値Ｖはこの組の有限状態マシンの各状態において与えられる。この態様で、図３Ａによる有限状態マシンの組は全体で１２の異なったカウント値を有し、それらのそれぞれは下で説明する方法に従って個別に制御される。
以下の例において、図３Ｄに従って文字ＸおよびシンボルＨ間の対応表が定められるように１組のメッセージが図１Ａに関連して説明した方法に従って解析されているものと想定する。理想的な場合では、文字Ｘは例えばＡＳＣＩＩコードで表され、文字のリストにはリストでの文字の数を指示する数が先行するであろうが、この例での簡略化のため対応表はアルファベット文字と３ディジットハミングコードとの間の直接対応表として示される。図３Ｄのリストは減少する相対頻度順の８つの文字と増大するハミング重み順の対応するハミングシンボルを示す。
図３Ｂに関して、ステップＳ２００は図３Ｆに示されるビットストリームのようなシーケン（逐次的）スビットストリームＹ＝ｙ1，ｙ2，ｙ3，・・・ｙnの形態のメッセージを受ける方法ステップを示す。次のステップＳ２１０において、推定器は最初のｍのディジットに対して入力ディジットｙiに等しい出力ディジットｅiを発生する。ステップＳ２２０において、値ｉはｍに設定される。
次のステップＳ２３０において、有限状態マシンの数ｋが設定される。換言すれば、ｋの異なった有限状態マシンからなる１組の有限状態マシンが定められる。各有限状態マシンは２mの状態を有し、各状態にはカウント値Ｖがある。ステップＳ２３０において、有限状態マシンの組の全てのカウント値Ｖは０に設定される。
有限状態マシンはマシンＭ1、Ｍ2・・・Ｍj・・・Ｍkが存在するように順序付けられる。図３ＢのステップＳ２４０に関して、次の処理手順が有限状態マシンＭj（ここで、ｊ＝（ｍ  ｍｏｄ  ｋ）＋１である）から開始する。選択された有限状態マシンにおいて、最初に状態Ｓ＝（ｙ1，ｙ2，・・・ｙm）が選択される。
この選択された状態において、値Ｖが読み出され（ステップ２５０）、その後（ステップ２６０）Ｖ＞０どうかのチェックがある。Ｖ＞０であれば、図３ＢのボックスＳ２７０によって指示されるように予測値ｐi+1が１に設定される。Ｖ＜０であれば、図３ＢのボックスＳ２８０によって指示されるように予測値ｐi+1は０に設定される。
図３Ｂと図３Ｅを参照して、次の入力ディジットｙi+1が読み出され（ステップＳ２９０）、出力値ｅi+1がｙｉ＋１とｐi+1モジュロ２とを加算することによってステップＳ３００によって計算される。このために、１＋１モジュロ２は０に等しく、１＋０モジュロ２は１に等しく、０＋１モジュロ２は１に等しくなる。
次に、ステップＳ３１０において、ディジットｙi+1のチェックがある。
ｙi+1＝１であれば、選択された有限状態マシンの選択された状態でのカウント値Ｖは図３Ｃのボックス３２０において示されるように１だけ増加され、すなわちＶ：＝Ｖ＋１となる。ｙi+1＝０であれば、選択された有限状態マシンの選択された状態でのカウント値Ｖは図３ＣのボックスＳ３３０において示されるように１だけ減少され、すなわちＶ：＝Ｖ−１となる。
その後、ステップ３４０において、次の有限状態マシンＭj+1が選択される。
この選択された有限状態マシンにおいて、ディジットｙi+1の値と前の状態とによって指示される状態が選択される（ステップＳ３５０）。これは１つの有限状態マシン内で１つの状態から他の状態に変えるために普通に使用されている態様で行なわれる。例えば、図３Ａを参照して、第１の有限状態マシン１１０での状態「００」から出発しかつディジットｙi+1が１状態である時には、状態「０１」が本発明に従って第２の有限状態マシン１２０において選択される。現在の状態が第２の有限状態マシン１２０で状態「０１」でありかつディジットｙi+1が１である時には、第３の有限状態マシン１３０での状態「１１」への推移となる。現在の有限状態マシンが最後の（ｋ番目）有限状態マシンであれば、第１の有限状態マシンでの状態への同一の態様の推移となる。
その後、インデックス値ｉはボックスＳ３６０によって指示されるように１だけ増大される。その後、受信ビットストリームＹに他の何かのビットが残っていれば、図３ＣのステップＳ３７０によって指示されるように制御が行なわれ、返答が「ｙｅｓ」であれば、選択された有限状態マシンの選択された状態でのカウント値を読み出してステップＳ２５０に再度進められる。他方、これがメッセージの最後のビットであったら、処理手順は終了する。
データ圧縮装置
図４を参照すれば、そこにはデータ圧縮装置２００の第１の実施例のブロック図が示されている。このデータ圧縮装置は変換されるべきメッセージの文字を受ける文字入力２１０を備えている。文字入力２１０はデータバス２３０により変換ユニット２２０に結合されている。データバスは本発明の一実施例に従って８ディジット文字を並列に変換することができる。本発明の他の実施例により、受信文字のディジットは変換ユニット２２０に直列に供給される。また、文字入力２１０において受信されるべき文字は他の数のディジットからなってもよい。変換ユニットは図２のステップＳ１１０およびＳ１２０に関連して上で説明した態様で低いハミング重みを有するシンボルに受信文字を変換するように設定されている。対応する文字よりも少ない数のディジットから構成されてもよいその結果のシンボルは出力２３４からバス２４０を介してシンボル対ビットストリーム変換器２５０の入力２４２に供給される。シンボル対ビットストリーム変換器２５０はその出力２５２でディジットｙiを有するビットストリームを推定器ユニット２６０の入力２５４に供給する。推定器ユニット２６０の目的は、メッセージの情報内容を保持している状態で、ビットストリーム内の値１を有するディジットの数を更に減少することである。推定器ユニット２６０はビットストリームＹ＝ｙ1−ｙnの受信に応じてビットストリームＥ＝ｅ1−ｅnを作る（ここで、ｎは推定器ユニット２６０に与えられるビットストリームのディジットの数である。ビットストリームＥは推定器ユニット２６０の出力２６２に供給される。ビットストリームＥは圧縮モジュール２７０に供給され、これはメッセージの情報内容を保持した状態でビットストリームのディジットの数を減少するように設定されている。この圧縮モジュールは例えばハフマンコード化のような圧縮アルゴリズムに従って動作する。１つの好適実施例によれば、静的ハフマンコードが使用される。このため、圧縮モジュール２７０はビットストリームＣ＝ｃ1−ｃr（ここで、ｒ＜ｎ）を発生する。圧縮ビットストリームＣはビットストリーム出力２８０に供給され、これは圧縮ビットストリームがメモリユニットに記憶されるようにそのメモリユニットに結合されてもよい。別態様として、ビットストリーム出力２８０は圧縮ビットストリームＣが他の電子ユニットに伝送されるように送信機ユニットに結合される。メッセージ内のビットの数の減少は伝送チャンネルのための帯域幅の要求を低下させ、それによって伝送効率を向上させる。
図５を参照すれば、推定器ユニット２６０がより詳細に表されている。推定器ユニット２６０はビットｙiにより構成されるビットストリームＹを受ける直列入力３００を備えている。受信ビットｙiはスイッチユニット３１０に供給され、これは最初のｍのディジットを出力３２０に直接スイッチするように設定されている。ビットストリーム入力３００は、また、モジュロ２加算器３５０の第１の入力３４０と遅延ユニット３５５を介して予測器３３０とに結合されている。遅延ユニット３５５は、それがビットｙi+1を受けるとビットｙiを供給するように１ビットを記憶する。予測器ユニット３３０は加算器３５０の第２の入力３６０に結合された出力を有している。加算器３５０は推定器ユニット出力３２０に結合された出力を有している。従って、推定器２６０は図３Ｂおよび３Ｃに関連して上で説明した方法を行なうように設定されている。
上で説明した態様で、予測器ユニット３３０は次のビットｙi+1の値の予測値ｐi+1を作るように設定されている。換言すれば、予測器ユニット３３０はｈ＜ｉ＋１に対して履歴値ｙhについての「推測値」ｐi+1に基づいてビットｙi+1がどんな値を有するかを「推測する」ように設定されている。「履歴」は有限状態マシンのカウント値によって与えられる（図３ＢのＳ２６０〜Ｓ２８０参照）。図５から、予測が正しければモジュロ２加算の結果ｅi+1が０になることが容易に理解される。
値ｅi+1は予測ビット値ｐi+1と実際のビット値ｙi+1との間のハミング距離を表す。従って、予測器が正しい予測値を作れば、２つの連続的なビット間のハミング距離ｅi+1は０となる。上のことから明かとなるように、表１を参照して、本発明による方法は極めて好都合の圧縮比を達成する。この長所の根拠の１つは上述した予測方法に従って正確な予測値ｐi+1を生じさせることである。
図９に関連して下に述べるように、復号方法は次のハミング距離ｅi+1の予測値を表す値ｐi+1を得るために既に復号したビット値ｙiを「履歴」として用いて同じ形式の予測を行なうことに基づいている。この予測復号方法は予測符号化が行なうのと同じ形式の予測を用いるため、復号の結果は正しいビットストリームＹとなる。
電子データ処理装置
図６を参照すれば、そこにはテキストメッセージのような情報の表示用のディスプレイユニット４１０を備えたデータ処理装置４００が示されている。データ処理装置４００は不揮発性メモリ４２０、マイクロプロセッサ４３０および読出し／書込みメモリ４４０を備えている。メモリ４２０はデータ処理装置４００の通常の機能を制御するコンピュータプログラムが記憶されている第１のメモリ部分４５０を有している。データ処理装置は例えば移動電話機のような携帯電子装置であってもよい。また、メモリ４２０はメッセージをコード化および／または復号するプログラムが記憶されている第２のメモリ部分４６０を含んでいる。他の実施例においては、メッセージをコード化および／または復号するプログラムは独立した不揮発性記録媒体４６２に記憶されている。このプログラムは実行可能な態様であるいは圧縮された状態で記録されてもよい。
以下において、マイクロプロセッサ４３０がある機能を行なう時には、これはマイクロプロセッサがメモリ４５０に記憶されているプログラムのある部分あるいは記録媒体４６２に記録されているプログラムのある部分を行なうことを理解されるべきである。
マイクロプロセッサ４３０はデータバス４７０を介してディスプレイ４１０に結合されている。データ処理装置のユーザにはディスプレイ４１０に表示されている文字によって情報メッセージが与えられる。例えば、電子装置の電池電圧がある値よりも低いことをマイクロプロセッサが決定した（これはマイクロプロセッサにメッセージ「電池交換」を表示することを促す）場合のようなある事象に応じて特定のメッセージが表示されてもよい。
マイクロプロセッサ４３０はデータバス４８０によってメモリ４２０に結合されており、またデータバス４９０によって読出し／書込みメモリ４４０に結合されている。また、マイクロプロセッサ４３０はデータバス５１０によってデータポート５００と通信を行なう。
図１Ａ、１Ｂ、２、３Ａ〜３Ｄに関連して説明した方法はメモリ部分４６０に記憶されているプログラムを行なうマイクロプロセッサ４３０によりそのマイクロプロセッサで行なわれることが可能である。図１Ａに関連して説明した方法に従って対応表を作成する命令に応じて、マイクロプロセッサはデータポート５００でのメッセージの受信を待機するように設定され、メッセージがデータポート５００で受けられると、文字が読出し／書込みメモリ４４０に一時的に記憶される。受信メッセージあるいはメッセージの受けた組の全ての文字が一時的に記憶された時に、マイクロプロセッサは異なった文字の数をカウントしかつ各文字に対する相対頻度を計算するように設定される。その後に、マイクロプロセッサ４３０は対応表を作成するように上で説明した態様でコードシンボルを異なった文字に割り当てるように設定される。
別態様として、マイクロプロセッサはデータポート５００を介して既製の対応表を受けかつその対応表を読出し／書込みメモリ４４０に記憶するように設定される。図１Ｂに関連して説明したように、対応表は文字数で始まりそれに同じ数の文字が続くリストに制限されてもよい。
その後に、マイクロプロセッサは図３Ｂに関連して上で説明した方法に従って減少したディジットビットストリームＥに受信メッセージあるいは受けた組のメッセージを変換する命令に応じてもよい。メッセージあるいはメッセージの組がビットストリームに変換されると、このビットストリームはメモリ４４０に記憶される。勿論、マイクロプロセッサは使用されるメモリを動作する最も効果的な態様に応じてあるいは他のハードウェアの配慮に応じてビットストリームＥをビット対ビットであるいは８ビット語にソートされて記憶されてもよい。
データ復元装置
図７を参照すると、データ復元装置６００の第１の実施例のブロック図が示されている。このデータ復元装置は多数のディジットｃiからなる圧縮ビットストリームＣを受ける入力６１０を備えている。入力６１０は逆圧縮モジュール６２０に結合され、これは情報内容を保持する状態でビットストリームＣをより長いビットストリームＥに伸長するように構成される。逆圧縮モジュール６２０は静的ハフマンコードに従って復号を行なうように設定されてもよい。
逆圧縮モジュール６２０は伸長ビットストリームＥを変換ユニット６３０に供給し、この変換ユニット６３０は上に説明された推定器２６０の機能の実質的に逆を行なうように設定されている。従って、変換ユニット６３０は多数のシンボルＨからなるビットストリームＹを直列に供給する。この目的のため、推定器２６０は図５のスイッチ３１０として機能するスイッチ６３２を含んでいる。遅延ユニット６３４は図５のユニット３５５と類似してビットｙi+1の受信時にビットｙiを供給し、予測器６３５は「履歴」値ｙiを受けることに応じて予測値ｐi+1を発生する。エンコーダ２６０の予測ユニット３３０がフィードフォワードの態様で結合されるが、デコーダ６３０の予測器６３５は出力Ｙが入力ビットストリングＥを復号するための「履歴」データとして使用されるようにフィードバックの態様で結合される。
変換ユニット６３０はビットストリームＹを出力６３８に供給するように設定されている。変換器６４０はビットストリームをシンボルに変換するため出力６３８に結合される。シンボルＨはデータバスを介して変換ユニット６５０の入力６４２に供給される。変換ユニット６５０は元のメッセージを復元するようにシンボルＨを文字Ｘに変換するように動作する。文字Ｘは変換ユニット６５０からを出力６６０に供給される。ポート６６０に供給される文字は例えば８ビットＡＳＣＩＩコードであってもよい。
メッセージを復元する方法
図８は本発明の一実施例に従ってメッセージＭを圧縮ビットストリームＣから復元する方法を示すフローチャートである。第１のステップＳ６００によれば、圧縮ビットストリームＣが受けられる。ビットストリームＣはハフマン復号のような復号／伸長のための既知の方法を用いてビットストリームＥに伸長される（ステップＳ６１０）。次いで、ビットストリームＥは本質的に図３Ｂおよび３Ｃに関連して説明した方法の逆を行なってビットストリームＹに変換される。
その後、ビットストリームＹは元のメッセージＭが復元されるように文字Ｘに変換される（ステップＳ６３０）。これはビットストリームＹをシンボルＨに分割し（ステップＳ６４０）、その後各シンボルＨを対応する文字Ｘに変換する（ステップＳ６５０）によって達成される。シンボルＨの文字Ｘへの変換は圧縮ビットストリームＣに更に含まれた対応表を用いて行なわれる。別態様として、変換表が予め設けられ、圧縮ビットストリームＣはメッセージに変換されるべき情報のみを含んでいる。シンボル対文字変換ステップの第３の実施例によれば、圧縮ビットストリームはメッセージ内の異なった文字の数と文字のリストとを備えているに過ぎない。変換表を得る目的のため、マイクロプロセッサ４３０（図６参照）のようなマイクロプロセッサがメモリ部分４６０（図６）に記憶されているプログラム内に与えられてもよい所定のアルゴリズムに従って各文字Ｘに対応するシンボルＨを計算するように設定されてもよい。
シンボルＨが文字Ｘに変換されてしまったら、その結果のメッセージが供給される。
図６を参照して、圧縮ビットストリームＣは不揮発性メモリ４２０のメモリ部分７００に与えられてもよい。メッセージ提示命令に応じて、マイクロプロセッサ４３０は、メモリ部分４５０内に記憶されているプログラムを用いて、メモリ４５０のプログラム部分７１０に記憶されていたデータ復元プログラムを逆圧縮する標準伸長アルゴリズムを使用してもよい。従って、メモリ部分７１０に記憶されているプログラムコードは伸長されてメモリ４４０のメモリ部分７２０に配置される。上述したように、メモリ４４０はランダムアクセスメモリＲＡＭであってもよい。その後、マイクロプロセッサはメモリ部分７２０からのデータ復元プログラムを実行することによって動作を続ける。データ復元プログラムの実行は不揮発性メモリ４２０のメモリ部分７００から圧縮ビットストリームＣを読出し、その後メッセージＭを構成する文字Ｘのストリームに圧縮ビットストリームＣを変換するように方法ステップＳ６１０、Ｓ６２０、Ｓ６４０およびＳ６５０を実行するステップを含んでいる。メッセージＭあるいはメッセージの部分はマイクロプロセッサ４３０によりデータバス４７０を介して遅延ユニット４１０に供給される。別態様として、状況に応じて、メッセージＭはデータバス５１０を介してデータポート５００に供給されてもよい。
図９Ａおよび９Ｂを参照すると、そこにはビットストリームＥのビットストリームＹへの変換（ステップＳ６２０）がどのようにして行なわれるかについて詳細に示されている。本明細書において、図９Ａおよび９Ｂに関連して説明される方法を予測復号方法と呼ぶことにし、図３Ｂおよび３Ｃに関連して上で説明した方法を予測符号化方法と呼ぶこととする。予測復号は、図９によるフローチャートを図３Ｂおよび３Ｃによるフローチャートと比較することによって明かとなるように予測符号化と本質的に同じ態様で行なわれる。従って、方法ステップＳ７００からＳ８７０は上で説明した方法ステップＳ２００からＳ３７０に本質的に対応する。復号と符号化との差は、本質的には、符号化方法においてディジットｙi+1は入力から読み出され（Ｓ２９０）ディジットｅi+1が計算されるが、復号方法ではその逆が行なわれることである。図９Ｂを参照して、入力ディジットｅi+1が読み出され、出力ディジットｙi+1が計算される。従って、復号方法のステップＳ８１０において、値ｙi+1についての問題は出力ディジットが１または０に等しいかどうかの問題に関連し、他方符号化方法においてはステップＳ３１０は入力値ｙi+1の値の問題に関連する。
図６を参照すると、メモリ部分７１０内のデータ復元プログラムは符号化および復号方法間の差を定めるプログラムルーチンに限定可能である。従って、一方でメモリに復号プログラムだけを記憶することと他方で復号プログラム並びに符号化プログラムを記憶することとの間でのメモリ空間の使用には極めて僅かな差しかない。更にまた、当業者は、プログラムそれ自体が好都合の少量のメモリ空間しか必要としない有利な程少数で数学的に複雑でないステップが上述のコード化方法および復号方法によって要求されるに過ぎないことを認識するであろう。そのため、本発明によりメッセージを復号しそして／または符号化するコンピュータプログラムはプログラムコードのためのメモリ空間の使用が装置のサイズに直接反映するような携帯電子装置には特に有利である。例えば、移動電話機において、極めて多数のメッセージをメモリに記憶する必要があり、各電話機はなるべくはユーザによって選択される人間の言語のメッセージを作るように設定可能とされるべきである。従って、本発明の目的は極めて多数のこのようなメッセージの組を移動電話機の不揮発性メモリの少量のメモリ空間に与えることである。本発明による復号プログラムはこのような少量のメモリ空間しか必要としないため、全ての異なった言語のメッセージがコード化状態で記憶されることができ、ユーザがメッセージを使いたい言語を選択すると、その選択された組のメッセージが上述した方法に従って復号される。予測符号化および／または予測復号プログラムの実行の間に、多数のカウント値Ｖがこのプログラムの実行の間に一時的に記憶される必要があるため、最大量のメモリ空間が使用される。各カウント値に対するビットの数をｃで表せば、カウント値を記憶するために必要なビットの数はｋ・２m・ｃとなる。好適実施例によれば、ｃの値は２または３に等しく選択されてもよい。
上述の実施例において、メッセージのハミング重みは圧縮のために好ましい符号化メッセージを与えるために減少される。好ましいハフマンコードは圧縮されるべきメッセージのハミング重みを小さくすればそれだけより有効的な圧縮を与える。しかしながら、ある異なったハフマンコードの選択によって圧縮されるべきメッセージのハミング重みが大きくなればそれだけより有効的な圧縮が達成される。従って、本発明によれば、文字のコードシンボルへの変換はコード化メッセージのハミング重みが最大化される態様で行なわれることができる。この場合に、予測符号化方法はそれが入力ビットストリームＹのものよりもより大きなハミング重みを有するビットストリームＥを発生させるように変更される。
通信ネットワーク
図１０は無線リンクを介して通信する２つのユニット７４０および７５０を含む通信ネットワーク７３５を示す。ユニット７４０はアナログ信号を発生するマイクロフォン７６０と、そのアナログ信号を多数の量子化範囲に量子化しコード語Ｈをそれら量子化範囲に割り当てる変換ユニット７７０とを含んでいる。
このため、アナログ信号を受けると、変換ユニット７７０はビットストリームＹの形態のコード語Ｈのシーケンスを供給する。１つの好適実施例によれば、ビットストリームＹは上で詳細に説明した形式の推定器ユニット２６０に供給される。推定器ユニットの出力Ｅは同様上で説明したように動作する圧縮モジュール２７０に供給される。圧縮モジュール２７０によって供給された圧縮ビットストリームＣはトランシーバ７８０に供給される。トランシーバ７８０はユニット７５０と通信を行なう例えばアンテナのような通信ポート７９０を含んでいる。
ユニット７５０は信号を受信して供給するトランシーバ８１０に結合した例えばアンテナのような通信ポート８００を含んでいる。トランシーバ８１０は圧縮ビットストリームＣを逆圧縮ビットストリームＥに変換する、上で説明した形式の逆圧縮モジュール６２０に結合される。逆圧縮ビットストリームＥは図７に関連して上で説明した形式のデコーダ６３０に供給される。デコーダ６３０の出力Ｙは変換ユニット８２０に供給される。変換ユニット８２０は受信ビットストリームＹをアナログ信号に変換し、これは例えばスピーカ８５０に供給される。
変換ユニット８２０はコントローラ８２５とメモリ８３０とを含み、メモリ８３０には変換表を含んだ変換情報が記憶されている。メモリ８３０はコード語Ｈの語長についての情報を保持している。その情報を用いて、受信ビットストリームＹはコントローラ８２５によりコード語Ｈに分割される。
コード語Ｈはその後デジタル対アナログ（Ｄ／Ａ）変換器８４０に供給される。Ｄ／Ａ変換器８４０はメモリ８３０内の変換表と共に働き、コード語Ｈによって定められる信号レベルを発生する。コード語Ｈが元の信号をサンプリングしたのと同一の周波数でＤ／Ａ変換器８４０に供給されると、Ｄ／Ａ変換器の出力は元のアナログ信号と同じになる。
変換ユニット７７０の機能は次の通りである。変換ユニット７７０は不均一確率密度の振幅を有するアナログ信号を受ける。例えば音声の振幅確率は０振幅で最大で、振幅の増大にしたがって減少する。このため、音声信号の量子化後は、最大確率量子化レベル範囲は最も低い振幅に対応するものとなる。Ａ／Ｄ変換信号Ｙのハミング重みを最小化する目的のため、コード語Ｈは値１を有するビットの数を最小にするように選択されなければならない。最少量の０を有するコード語をアナログ信号に割り当てるコード化方式は米国特許第５，０６２，１５２号に記載されており、その内容はこれによって参照として組み入れられる。
有利なことに、変換ユニット７７０によって供給されるデジタル信号Ｙはコード語Ｈの語長を量子化レベルの必要数ｒに適合させることによって最小化されることができる。例えば、ｒ＝６４量子化レベルを持つだけで十分であれば、コードシンボルは６つのビットを含むことだけを必要とする。量子化レベルの数が６５と１２８との間にある場合には、７ビットの語長が必要である。ｄビットを有する語によって定義可能な量子化レベルの数ｒは次のようになる。
ｒ＝２d
従って、コード語Ｈ内のビットｄの必要数は次式を用いて定めることができる。
ｄl＝ｌｎ（ｒ）／ｌｎ２
結果ｄlが整数でなければ、ビットｄの数は最も近い高位の整数にｄlを切り上げることによって定められる。例えば、量子化レベルの必要数がｒ＝１９０である場合には、結果はｄl＝ｌｎ（１７０）ｌｎ２＝７．４０９となる。ｄlをその最も近い高位の整数に切り上げればｄ＝８となる。従って、コード語Ｈ内のビットの必要数はｄ＝８となる。コード語Ｈの語長はユニット７５０に伝送され、メモリ８３０に記憶される。この変数ｄは、コード化メッセージを受けるとビットストリームＹを正しい長さのコード語に分割するコントローラ８２５によって使用される。
量子化信号範囲の必要数はアナログ信号および振幅分解能の最大振幅に依存する。アナログ信号の高忠実度再生のため、レベル範囲は高振幅分解能を達成するように小さくなければならず、このため極めて多数の量子化信号レベルを使用する必要がある。
アナログ信号の最大振幅を定める目的のため、この信号がある時間機関の間測定される。振幅分解能は手動的あるいは自動的に設定されることができる。コード語の語長を履歴最大振幅および選択振幅分解能に適合することによって、デジタル信号Ｙ内のビットの数は最小化される。
変換ユニット７７０は量子化信号範囲およびコード語間の対応リストすなわち変換表を発生する。このリストは変換ユニット７７０と共に働くメモリ８６０に記憶される。メモリ８６０に記憶されたリストは定められた索引に従ってコード語Ｈを量子化信号範囲に割り当てるために使用される。
更に、索引リストおよび語長ｄは変換ユニット７７０からユニット７５０への伝送のためトランシーバ７８０に供給される。トランシーバ８１０が索引リストを受けると、このリストはメモリ８３０への記憶のため変換ユニット８２０に供給される。その後、メモリ８３０に記憶されたリストはコード語Ｈによって規定される信号レベルを発生するためにＤ／Ａ変換器によって使用される。
通信ネットワーク７３５の他の実施例によれば、コード語Ｈを含むコード化メッセージは図１０の点線８７０によって表されているように変換ユニット７７０からトランシーバ７８０に直接的に供給される。その実施例において、受信ユニットは、また、変換ユニット８２０およびトランシーバ８１０間の直接接続を与える。
通信ネットワーク７３５のなお他の実施例によれば、コード語Ｈを含むコード化メッセージは変換ユニット７７０から圧縮モジュール２７０に直接的に供給される。この直接接続は図１０で点線８８２によって表されたデータバスによって得られる。ユニット７５０は逆圧縮モジュール６２０および変換ユニット８２０間の直接接続を与える対応するデータバス８８４を含んでいる。データバス８８４による直接接続は変換ユニット７７０によって供給される符号化メッセージ内のビットの数の減少を可能にする。
更に他の実施例によれば、推定器ユニット２６０とトランシーバ７８０との間に直接接続８９０が設けられ、それによってビットストリームＹよりもより少ない０を保持するビットストリームＥの転送が可能となる。従って、この実施例は不均一確率密度を有する音声あるいは音楽のような信号を伝送するために必要な電力を更に減少する長所を有している。ユニット７５０はトランシーバ８１０およびデコーダ６３０間の対応する直接接続９００を含んでいる。
勿論、ユニット７４０は同じようにコード化信号を受けてこのような信号を復号するように適合されてもよい。このために、ユニット７４０は上に説明した部分６２０、６３０、８２０、８２５、８３０、８４０および８５０と同様の部分を含んでもよい。同様にユニット７５０は上で説明した態様でアナログ信号を符号化するように適合されてもよい。
【図１Ａ】
0003995106.tif 000003
【図１Ｂ】
0003995106.tif 000004
【図２】
0003995106.tif 000005
【図３Ａ】
0003995106.tif 000006
【図３Ｂ】
0003995106.tif 000007
【図３Ｃ】
0003995106.tif 000008
【図３Ｄ】
0003995106.tif 000009
【図３Ｅ】
0003995106.tif 000010
【図４】
0003995106.tif 000011
【図５】
0003995106.tif 000012
【図６】
0003995106.tif 000013
【図７】
0003995106.tif 000014
【図８】
0003995106.tif 000015
【図９Ａ】
0003995106.tif 000016
【図９Ｂ】
0003995106.tif 000017
【図１０】
0003995106.tif 000018