JPH0427733B2 - - Google Patents

Description

請求の範囲 １ 所望のデジタルフオーマツトデータ・ストリ
ームを時間領域での推定分散サンプルに変換した
入力データ・ストリームを有するデジタル或はア
ナログデータのブロツクを実時間データ圧縮する
装置であつて、 前記デジタルデータ・ストリームに接続され、
個々の推定分散サンプルにデジタルビツトを割当
て、前記サンプルの限界回帰（マージナル・リタ
ーン）を計算する高速計算手段と、 前記各サンプルのマージナル・リターン及び前
記各サンプルの推定分散値同士を比較する比較手
段と、 前記高速計算手段と前記比較手段に接続された
高速記憶手段と、 前記高速計算手段に接続され、前記デジタルデ
ータサンプルの最大マージナル・リターンを計算
するのに使用される予め決定された最小自乗誤差
定数を記憶するルツクアツプテーブル手段と、 前記高速記憶手段と前記ルツクアツプテーブル
手段に接続されたアドレス生成手段と、そして 前記計算手段と前記比較手段及び前記アドレス
生成手段とに接続され、前記高速計算手段よりの
圧縮されたデータサンプル・ブロツクの実時間ス
トリームを提供するためのコマンド列を提供する
制御手段とを備え、 前記圧縮されたデータのブロツクのそれぞれは
圧縮されたデータの各ブロツクに割当てられるべ
き所定数のビツトと、最大マージナル・リターン
を有するサンプルに最適にビツトを割当て、圧縮
されたデータの各ブロツクが最小ビツトエラーレ
ートと最大の平均マージナル・リターンを有して
いることを特徴とする実時間データ圧縮装置。 ２ 前記高速計算手段は、入力データとしての前
記入力データ・ストリームのデジタルデータサン
プルのそれぞれの前記推定分散を前記高速記憶手
段に記憶するように、前記制御手段によりプログ
ラムされていることを特徴とする請求項第１項に
記載の実時間データ圧縮装置。 ３ 前記高速計算手段は、入力されるデータの１
ブロツクを表わす予め定められた数のデジタルデ
ータ・サンプルを検出して圧縮するように、前記
制御手段によりプログラムされていることを特徴
とする請求項第２項に記載の実時間データ圧縮装
置。 ４ 前記デジタルデータのサンプルは前記高速計
算手段により個々に検査され、種々のサンプルに
対して異なるビツト数を割当てることによつて、
前記圧縮されたデータブロツクに対して予め定め
られたデータ圧縮比を提供するように圧縮される
ことを特徴とする請求項第３項に記載の実時間デ
ータ圧縮装置。 ５ 前記高速計算手段は圧縮されるべきデータサ
ンプルの推定分散を計算し、データブロツクの推
定分散を大きさが減少する方向に並べるかえるよ
うにプログラムされていることを特徴とする請求
項第３項に記載の実時間データ圧縮装置。 ６ 前記高速計算手段は１つのブロツクデータの
各サンプルに対してマージナル・リターンを計算
し、前記ルツクアツプテーブル手段に記憶されて
いる定数を前記推定分散に乗算して、最大マージ
ナル・リターンを有するサンプルを決定するよう
にプログラムされていることを特徴とする請求項
第５項に記載の実時間データ圧縮装置。 ７ 前記高速計算手段は、最大マージナル・リタ
ーン値を有しているサンプルに、割当てられるべ
きビツトの１ビツトを割当てて、最大のマージナ
ル・リターンを有するサンプルのマージナル・リ
ターンを再計算するようにプログラムされている
ことを特徴とする請求項第６項に記載の実時間デ
ータ圧縮装置。 ８ 前記高速計算手段は、割当てられるべきビツ
トの全てが前記サンプルに割当てられて最大マー
ジナル・リターン値に最適にビツトが割当てられ
るまで、最大マージナル・リターン値を有するサ
ンプルに、割当てられるべきビツトの１ビツトを
一度で割当てるようにプログラムされていること
を特徴とする請求項第７項に記載の実時間データ
圧縮装置。 ９ 前記高速計算手段は、各サンプルに割当てら
れたビツト数により前記サンプルのそれぞれを符
号化するようにプログラムされており、これによ
り、同じブロツクのサンプルが異なる圧縮比で圧
縮されることを特徴とする請求項第８項に記載の
実時間データ圧縮装置。 １０ 乗算により高速に除算を実行するために前
記計算手段に接続され、推定逆数を記憶した複数
の除算用ルツクアツプテーブルをさらに有するこ
とを特徴とする請求項第１項に記載の実時間デー
タ圧縮装置。 １１ 前記アドレス生成手段と前記比較手段に接
続され、２分されたポインタ・アドレス計算を実
行できる２分レジスタをさらに有することを特徴
とする請求項第１項に記載の実時間データ圧縮装
置。 １２ 入力データストリームを実時間でデータ圧
縮する方法であつて、 デジタルデータのブロツクをデジタル要素のサ
ンプルに分割する工程と、 デジタル要素サンプルの推定分散を計算する工
程と、 前記デジタルデータのサンプルを推定分散の大
きさが小さくなる順に並べる工程と、 デジタルデータの各サンプルを調べ、最大マー
ジナル・リターンを有するサンプルを決定する工
程と、 前記デジタルデータのブロツクを規定するため
に割当てられる予め定められた数のビツトのうち
１ビツトを割当てることにより、最大マージナ
ル・リターンを有するサンプルのマージナル・リ
ターンを減少させる工程と、 割当てられるべきビツト数を表しているポイン
タを、最大マージナル・リターンを有している所
定のサンプルから次に最も低いサンプルに、サン
プルが配列されている順に移動する工程と、 最大マージナル・リターンを決定し、１ビツト
を割当てることによつて最大マージナル・リター
ンを有するサンプルのマージナル・リターンを減
少し、割当てられるべきビツトの全てが割当てら
れるまで、所定のサンプルに割当てられるビツト
数を表すポインタを移動する工程を繰返す工程
と、そして 実時間で個々のサンプルのそれぞれに割当てら
れるビツト数で前記サンプルのそれぞれを符号化
する工程と を有することを特徴とする実時間データ圧縮方
法。 １３ 前もつてデジタルデータのブロツクを定義
するために割当てられるビツト数を予め決定して
データ圧縮の圧縮比を定義する工程をさらに有す
ることを特徴とする請求項第１２項に記載の実時
間データ圧縮方法。 １４ デジタルデータ・ブロツクのスペクトル・
エネルギー特性を規定するサイド情報を決定する
工程と、前記サイド情報を用いて各サンプルを符
号化する符号化工程をさらに有することを特徴と
する請求項第１３項に記載の実時間データ圧縮方
法。 １５ 入力データストリームを実時間でデータ圧
縮する方法であつて、 データの入力ストリームをデジタルデータのブ
ロツクに分割する工程と、 前記デジタルデータ・ブロツクをデジタル要素
のサンプルに分割する工程と、 デジタルデータの各サンプルを調べ、各サンプ
ルのエネルギー量を決定する工程と、 前記エネルギー量が小さくなる順に前記サンプ
ルを並べる工程と、 前記サンプルをデジタルで定義するために１つ
あるいはそれ以上のビツトで１つのサンプルを定
義するのに適用できる、エネルギー量に関連した
累積利得を決定する工程と、 １つのサンプルを定義するのに使用する最大ビ
ツト数を決定する工程と、 順番に並べられたサンプルに関連して固定比を
有する基準マーカと他のマーカを位置付ける工程
と、 マーカの間のサンプルに、それらサンプルが並
べられた順番にビツトを割当て、最適なビツト割
当てを行う工程と、 デジタルデータのブロツクを定義するために割
当てられる全ビツト数が割当てられたかどうかを
チエツクする工程と、 デジタルビツトを最適に割当ててデジタルデー
タの前記ブロツクの要素の各サンプルを符号化す
る工程と を有することを特徴とする実時間データ圧縮方
法。 発明の技術分野 この発明は、伝送される圧縮されたデジタルビ
ツトの最適な割当てを実現するために、適応変換
符号化（Adaptive Transform Cod−ing：
ATC）を使用して、標準的な商業用のデータリ
ンクにより伝送するためにアナログあるいはデジ
タルデータを圧縮するためのデジタル装置と方法
に関するものである。特に詳しくは、実時間での
データ圧縮と伝送を可能にする情報ブロツクを定
義するために、高速にビツトの割当てを行なうこ
とができるハードウエアに関するものである。 従来技術の説明 デジタルの通信フオーマツトは、多くの点で伝
統的なアナログフオーマツトよりも優れている。
その結果、アナログ電話回線を全てがデジタル信
号である回線に変更する傾向にある。高品質の音
声はアナログ形式で約3200Hzの帯域を有してい
る。このアナログ音声信号をデジタルフオーマツ
トに変換している現在の方法は、音声を１秒当り
8000サンプルからなるブロツクでサンプリング
し、サンプル当り８ビツトを用いて各サンプルに
デジタル値を割当ている。この一般的な変換は、
復号化時、電話の音質で音声波形を再生するため
に、64Kbpsで伝送できる帯域を必要としている。
これが、標準的なデジタルデータ電話回線が
64Kbpsのデータレートで標準化されている最も
重要な理由である。 １秒当り64000ビツトを伝送できる標準的なデ
ジタル音声電話回線は、一般に電話音声の伝送に
使用されている。デジタル電話回線が採用される
と、64Kbpsの伝送能力の全てがユーザにより所
望の方法で使用される。このような標準的な電話
データ回線を使用し、少し音声の質が低下するけ
れども、会話が理解できる程度に、デジタル的に
同じデータ回線上に最大８つの音声チヤネルを伝
送することが可能である。さらにまた、デジタル
データ表現を１／４に圧縮し、ほとんど音質を低
下させることなく、４つの音声チヤネルを１つの
デジタルデータ音声回線に伝送することができ
る。今までは、そのような音声データを圧縮する
遅延時間のために、実時間の伝送に使用するのが
見送られてきていた。 大陸横断のデジタル通話回線は、１月当り
40000ドル以上の賃貸あるいはリース量を必要と
する。もし伝送される音声が１／４の圧縮されれ
ば、ユーザは１月当り120000ドル以上を節約でき
ることになる。 25年以上の間、学者の論文は音声情報を圧縮す
る種々の方法を提案してきている。しかし、圧縮
された音声情報を伝送するとき、上述した節約を
実現できる利点を備えたいかなる装置も、現在市
販されていない。 HuangとSchulthiessは、その論文“相関のあ
るガウス分布のランダム変数のブロツク量子化”
（Block Quantization of Corre−lated
Gaussian Random Variables）（IEEE Tran.−
Comm.Sys.Vol.CSII.pp.286−296.1963年９月）
で、デジタル情報のブロツクは１つずつのサンプ
ルを基本に符号化され、さらにデータ圧縮を行う
情報ブロツクを定義するのに、デジタルビツト割
当てることを提案している。この論文で提案され
たビツト割当ては、次善の方法である。なぜな
ら、ビツトｂ（ｊ）の最適な分布は、分散σ²（ｊ）
の線形な関数でなく、実際のビツト配分において
滅多に生じない非整数のビツトが割当てられるよ
うに要求しているためである。 adrian Segalは彼の論文“ベクトルソースの
ビツト割当てと符号化”（Bit Allocation and
Encoding for Vector Sources）（IEEE Trans
Inform Theory Vol.IT−22，pp.162−169，
1976年３月）で、デジタル情報のブロツクのデー
タ圧縮を実現するためにデジタルビツトを割当て
る異なる方法を吟味している。さらに、この
Segalの論文は、デジタル情報のブロツクをデー
タ圧縮するために、個々のビツトを最適に割当て
るためのアルゴリズムを提案している。この論文
は最適なビツト割当てを提案する一方、それを実
施するのに約60000回のコンピユータの動作を必
要としている。本願発明において同様なビツト割
当てを実行するには、実時間での簡単な動作とし
て実行されうる約7560動作のみを必要とするだけ
である。 ベル研究所のRichard V.CoxとRonald
Crochiereらは、その論文“適応変換符号化
（ATC）の実時間シミユレーシヨン”（Real
Time Simulation of Adaptive Transform
Coding）（IEEE Trans.on Acoustic.Speech
and Signal Processing.Vol.ASSP 29，No.２，
1981年４月）で、低いビツトレート（9.6−
16Kbps）で64Kbpsの音声ラインに伝送する音声
のデジタル符号化の効果的な手段として、適応変
換符号化（ATC：Adaptive Transform
Coding）を提案している。 実際の電話における会話は、圧縮されたデータ
と符号化されて変換されたデータとからなつてい
た。符号化されたデータは伝送され、その変換さ
れたデータは受信側で、圧縮されたデータ形式か
ら復号される。このCoxその他の論文は更に、
ATC符号化と、実時間でのデータ圧縮伝送がで
きる高速のプロセツサを用いたデコーダ（復号
器）を教授している。

【図面の簡単な説明】

第１図は一般的な従来の符号化技術を示すブロ
ツク図、第２図は適応変換符号化（ATC）の従
来技術を示す概略ブロツク図、第３図は最適な高
速データ圧縮を実現する、好適な実施例のビツト
割当てのポインタ方法を示すフローチヤート、第
４図は好適な実施例のポインタシステムが高速に
ビツトを割当てるために、どのように実行される
かを示す概略図、第５図は最適な高速のデータ圧
縮を実現するためのビツト割当てのマーカー方法
を用いて第３図の好適な実施例を修正して示した
図、第６図は限界回帰（マージナリ・リターン：
marginal return）データがどのように推定分散
データ（estimated variance data）に関連して
いるかを示す、変換されたデータブロツクの推定
分散データの大きさをグラフで表した図、第７図
は高速データ圧縮システムがデジタルやアナログ
データに対して、いかに使用されるかを示すブロ
ツク図、第８図は好適な実施例の高速データ圧縮
システムを例示した簡単なブロツク図、そして第
９Ａ図と第９Ｂ図は、周波数領域変換（FDT）
を実行でき、線形予測符号化（LPC）モデルを
作成し、そのLPCモデルよりの推定分散値を計
算し、限界回帰計算に基いてビツトを割当てるシ
ステムを示している好適な実施例の第８図をより
詳細に示した図である。 好適な実施例の説明 図面を詳細に説明する前に、使用されるデータ
回線は電話会社によつて64Kbpsのレートでクロ
ツクされているため、伝送されるべきデータはこ
のクロツクレートに従わねばならない。 ここでは、この発明の説明を簡単にするため
に、圧縮されるべきデータブロツクは、256サン
プルに分割されているものとし、それらの各々は
データ圧縮器に入力される線上の12ビツトで定義
されているものとする。このことは、64Kbpsの
レートの出力データを提供するためには、
96Kbpsのビツトレートで処理されて出力される
ことを意味している。この発明のシステムはま
た、各チヤネル当りの出力は16Kbpsであるが、
ハードウエアデータ圧縮器で96Kbpsの入出力デ
ータレートを有することができる。 各サンプルのそれぞれが、12ビツトでなく６ビ
ツトで定義されているとすると、６ビツトで伝送
することにより、実際上１／２のデータ圧縮とな
る。音声データは非常に複雑なスペクトル（周波
数域）を有しているため、各サンプルを定義する
のに、サンプルに等しくビツトが割当てられるも
のでなく、音声周波数域の解析を必要とする。本
願発明は、入力されるデータブロツクの256サン
プルを定義するのに使用され、64Kbpsである音
声データリンク・ラインのデータレートに基づい
て１／４の圧縮比を得ることができるように、１
秒当り16Kbpsで再伝送される約400ビツトを最適
に割当てようとするものである。 まず、前述したAdrian、SegallのIEEEの論文
に開示された基本的な符号化の概要１０を示して
いる第１図を参照する。この符号化処理は、スカ
ラソースに対する既知の符号化手法を利用して、
ベクタソースに適合して設計されている。著者
は、線１１上の入力X⁽ⁱ⁾を、ガウス分布を有して
いる独立して一様に分布したｍ次元のランダムベ
クトル列で構成された離散したメモリのないベク
トルソースよりの出力として説明している。ベク
トルX⁽ⁱ⁾は“０”でない行列式Ｓ１２によりY⁽ⁱ⁾ベ
クトルに変換され、相関のないＹベクトル成分を
形成している。Ｙベクトルのｍ個の成分のそれぞ
れはソース符号化技術によりエンコーダ１３，１
４，１５で符号化され、個々のノイズのないチヤ
ネル１６を通して、復号を行なう装置にデジタル
値を提供するために伝送される離散的な（個々
の）デジタル値Y^を提供している。受信された線
１７上のデジタル値Y^は、“０”でない行列式Ｒ
１８で逆変換され、線１１上の元の信号X⁽ⁱ⁾に近
似しているX^ベクトルを線１９上に出力される。 チヤネル１６を通して伝送される線１１上のソ
ース情報は、限定されたデジタルビツト数を有
し、ソースワードあるいはブロツクの各成分ある
いはサンプルは個々に処理されることを、Segal
は認識していた。この問題は、ソース情報X⁽ⁱ⁾と
再生された数列X^との間の、全体的な最小自乗誤
差を最小にするために、個々の成分あるいは要素
に対し最適なビツト割当てを見出すことであつ
た。 Segallは有効なビツトを最適に割当てるための
１つの手順を提案している。まず最初に、限界回
帰値（marginal return value）Ｐ（ｂ，ｋ）が
各サンプルに対して計算される。それから、それ
ら限界回帰値は降順に配分される。最も高い限界
回帰値を有しているサンプルには１ビツトが割当
てられ、それよりも少ない限界回帰値Ｐ（ｂ，ｋ）
は、そのビツトを受け取るサンプルのために再び
計算される。それから、サンプルは限界回帰値が
小さくなる順に再び並べられ、次のビツトは次に
最も高い限界回帰値を有するサンプルに割当てら
れる。その処理は有効ビツトの全てが割当てられ
るまで繰返し実行される。それから、割当てられ
たビツトは、そのサンプルを符号化するのに使用
され、そのサンプルはデジタルフオーマツトで１
つのブロツクで伝送され、受信側で復号される。
この手順は、ほぼ60000回のソーテイングやマー
ジング（併合）など、を必要とし、好適な変換処
理を使用し、256サンプルに亙り400ビツトを割当
てるのに、この手順では約60000回のソーテイン
グとマージング（併合）などの操作を必要として
いる。 次に、前述した従来技術のCoxとCrochiereの
IEEEの論文に開示された適応変換符号化２１の
ブロツク図を示している第２図を参照する。線２
２上のデータ列X⁽ⁱ⁾はバツフア２３にブロツク単
位に格納される。X⁽ⁱ⁾ベクトルは、ブロツク２４
で周波数領域変換（FDT）され、ブロツク２５
で量子化されて符号化され、ブロツク２６で複合
された後、ノイズのないチヤネル２７を介して伝
送される。 サイド（副）情報（side information）はブロ
ツク２８で計算されて量子化される。バス２９上
のサイド情報は、伝送のためにチヤネル２７を介
してマルチプレクサ２６に送られ、また、情報ブ
ロツクの特性のスペクトルを推定するのに使用さ
れる。個々の量子化されたサンプルに対するビツ
ト割当ては、ブロツク３１で行なわれる。各サン
プルに割当てられたビツトはエンコーダ２５で符
号化され、バス３２を介してマルチプレクサ２６
に送られる前に、ステツプサイズ値△ｋが符号化
されたビツトに付加される。 次に、好適な実施例のビツト割当てのポインタ
方法を例示している論理フローチヤートの第３図
を参照する。 入力されるデータは、ビツトを割当てるのに必
要な推定分散データ（estimate variance deta）
σ²（Ｋ）を提供するためにブロツク３３で処理さ
れる。推定分散データはサンプルのそれぞれに対
して記憶され、メモリからシステムに供給され
る。これにより、より詳しく後述するように、シ
ステムはブロツク３４で推定分散データをその値
の小さい順に並べ換える。ソートされた情報はま
たメモリに格納され、ブロツク３５で示されるよ
うに、システムにより予め定められた数のポイン
タを推定分散データの最上位（先頭）にセツトす
るのに利用される。それからブロツク３６で示す
ように、システムは推定された分散データを使用
して簡単な計算を実行し最大限界回帰値を決定す
る。この値はポインタによつて指示されたそれぞ
れの大きさや値に対してＰ（ｂ，ｋ）として定義
される。ブロツク３７は、割当てられるべき400
ビツトのうちの１ビツトが、最も高い限界回帰値
を有しているポインタのみに対する大きさや値に
割当てられることを示している。ブロツク３８
は、ポインタが推定された分散の最高（次の最小
の）大きさあるいは値の次に移動されることを示
している。ブロツク３９では、割当てられるべき
400ビツトの全てが割当てられたかをシステムが
判断し、そうでなければ線４１によりブロツク３
６へ戻り、最高あるいは最大の限界回帰値を再び
計算して求める。システムは再びブロツク３７で
最高の限界回帰値に他のビツトを割当て、ブロツ
ク３８でポインタを次の最小の推定分散値に移動
させる。システムはまた割当てられるべきビツト
の全てが割当てられたかどうかを判定し、割当て
られるべき全てのビツトが割当てられるまでルー
プ４１を介して３６に戻る。そして、システムは
ブロツク４２でビツト割当てを終了する。ポイン
タシステムでは、最も大きい推定分散の大きさや
値に、より多くのビツトを割当てて、システムの
能力を効率よく最大限に利用し、伝送する情報ブ
ロツクを最適に定義できる。 第３図の論理フローチヤートの動作例として、
限界回帰あるいは限界誤差（marginal error）
が、下式より１あるいはそれ以上のビツトを増や
すために理論的に決定される。 Ｐ（ｂ，ｋ）＝σ²（ｋ）［φ（ｂ−１）−φ(b)］ ここで、ｂは割当てられるビツト数を示し、ｋ
はインデツクスとしての係数である。σ²（ｋ）は
ｋ番目の係数に対する推定分散で、φ(b)は分散が
１のガウス分布したランダム変数をｂビツトで量
子化したときに得られる最小自乗誤差（mean−
squared error）である。 項［φ（ｂ−１）−φ(b)］は、各ビツト(b)に対す
る定数で、計算されてメモリあるいは高速のアク
セスのためにルツクアツプテーブルに記憶され
る。推定分散が正規化され、あるいは推定分散σ²
（ｋ）によつて伝送係数y⁽ⁱ⁾を割ることにより単位
元（unity）になるとき、限界回帰値は推定分散
σ²に、各ビツト(b)に対して予め計算されている最
小自乗誤差を掛けることにより計算される。この
最小自乗誤差項は、１ビツトｂを付加することに
より限界回帰値Ｐ（ｂ，ｋ）を向上させ、あるい
は大きくする利得量を表しているため、累積利得
（cumulative gain）と呼ばれる。ビツト数を０
から１に、１から２に、２から３にというように
増やすことによる利得の例を以下に示す。

【表】

【表】 第３図におけるサンプルに対する限界回帰は、
最大あるいは最高位の限界回帰値に新たなビツト
を割当てるために、ブロツク３７で計算されなけ
ればならない。ビツト(b)の数が０のときは、いか
なる係数ｋに対する限界回帰も分散に等しくな
り、Ｐ（ｏ，ｋ）＝σ²（ｋ）となる。時間領域のサ
ンプルが推定分散σ²（ｋ）が小さくなる順に並ん
でいると、ソートされている推定分散値の順番を
並びかえたり、マージングすることなくビツトを
配置したり、割当てたりすることができる。 第４図は、メモリや第３図のブロツク３４で発
生するであろう分散σ²の図４３を示している。最
初、ポインタの全てはブロツク３５（第３図）で
示されたように、最大の推定分散データの先頭に
セツトされている。10個のポインタは、矩形に１
から10の番号が付され、前述したサンプルを指示
するための矢印とともに示されている。矩形の中
の数字は個々のサンプルに割当てられるビツト数
を表している。各サンプルに１以上のビツトを割
当てて得られる利得量は、利得項Ｇ＝Ｘ（B_K-1−
B_K）で表される。ここで、累積利得項は予め計
算されてメモリに記憶されている。全てのポイン
タは最初順番に並べられたサンプルリストの先頭
にあり、サンプルはビツト割当ての処理を通し
て、最初にソートされた順番を維持している。こ
うして、その順に並んでいる他の要素の前にその
最初のビツトを受け取るいかなるサンプルあるい
は要素はまた、その順に並んでいる同じ他の要素
の前にその第２のビツトを受け取る。 第４図は、推定分散（σ²）のリストの先頭の要
素（サンプル）が全て６ビツトよりも少なくない
ビツト受け取つたことを示している。これは、６
ビツトポインタが要素２の位置に下がつたとき
は、ポインタ６より上の要素の全てには６ビツト
が割当てられたことを示しているためである。要
素０がその７番目のビツトを受け取ると、ポイン
タ７は要素１に下降する。このように、ポインタ
７を要素１に移動することにより、要素０には７
ビツトが割当てられる。ポインタは、全ビツトが
割当てられるまで、一回に１つしか移動しない。
全ビツトが割当てられた後、ベクトルY⁽ⁱ⁾が量子
化され、第２図を参照して説明したように、符号
化に用いられるビツトとともに符号化される。 次に、ブロツク内のサンプルにビツトを割当て
る、好適な実施例のマーカ方法を示す第５図のフ
ローチヤートについて説明する。入力したデータ
はブロツク３３で処理され、推定分散σ²（ｋ）デ
ータを出力し、そして、ブロツク３４で推定分散
データの大きさや値が減少する順に並べられる。
より詳しく後述するように必ずしもマーカ値であ
ることを必要としないビツトの割当てを実行する
ために、ブロツク４４でシステムは推定分散によ
つて参照値を計算する。 第２の計算はブロツク４５で実行され、ともに
１つの組あるいはグループにまとめられる１組あ
るいは１グループの推定分散に割当てられるいく
つかのビツトに関連した、新しいマーカの値を提
供している。第２の計算はブロツク４５で行なわ
れる。マーカの比に関連して、そのマーカが何処
に位置するかを計算したのち、マーカはブロツク
４６で位置決めされ、ブロツク４７で、位置決ま
されるべき最大数のマーカが位置決めされたかが
判定される。全てのマーカが位置決めされていな
いと答えは“NO”となり、線４８を通りフロー
はループに入り、ブロツク４７で示されたよう
に、マーカの全てが位置付けされるまで、配置さ
れたあるいは既知の比に関連した新たなマーカの
計算が続けられる。全てのマーカが位置付けされ
ると、システムは現在その位置にあるマーカを計
算する。この計算が実行された後、ブロツク５１
で、以前の計算が割当てられるべきビツトの全て
を割当てたかどうかを判定する必要がある。答え
が“NO”であれば、システムは線５２のループ
に入り、ブロツク４４で推定分散に対する新たな
参照値の計算に戻る。それからループを通り、ブ
ロツク５３に進むまでそのループを実行する。ブ
ロツク５３ではビツトの割当てが終了し、システ
ムはブロツク５４で停止する。 マーカ方法の動作の一例を、第６図を参照して
説明する。この第６図は、縦軸に推定分散の大き
さや値を、横軸にブロツクデータを構成するデー
タのサンプルをとつたグラフ形式で示した図であ
る。縦線５５〜６７は大きさが小さくなる順に並
べられたサンプルの推定分散の順番に並べられた
値を示しており、このチヤートあるいはグラフで
表される256個のサンプル全てを示すために、そ
れらの新しいアドレスには０から255の番号が付
されている。 順番に並べられたアドレスの数値は、縦線５７
〜６７の下の新たな位置アドレスと、元の位置ア
ドレスで示されており、データのサンプルの元の
位置は並び替えられ、元のデータサンプルは依然
として、メモリにおけるそれらに関連する元の連
続したアドレスを保持していることを示してい
る。第２の軸あるいは縦座標軸の目盛は、Ｙ軸６
８に限界回帰比を表している利得スケールに重ね
合わされて示されている。限界回帰比に示された
値は、第３図や第５図のフローチヤートに関連し
て使用されたのと同じ技術用語を使用したビツト
マーカやポインタによるものである。縦線５５は
８ビツトマーカと７ビツトマーカとの間にあり、
７ビツトを受け取る推定分散の大きさを有してい
るように、８ビツトマーカの下にあることに注目
されたい。縦線５６，５７および５８のそれぞれ
は、推定分散値が６ビツトを受取る範囲内にあ
る。縦線５９と６１はそれぞれ５ビツトと４ビツ
トの範囲内の最高の位置で示されており、割当て
られるビツトの値はそれよりも少なくなる。推定
分散の大きさの値は、入力するデータの種々の形
式に対して変えられることが理解されよう。限界
回帰比６８の目盛は固定であるが、ビツトマーカ
あるいはビツトの間の比は統一されておらず、全
てのサンプルをカバーするために調整される。こ
うして、マーカ方法は効率よく限界回帰比の目盛
６８を調整し、ポインタの分布に関して前述した
ように、個々のサンプルの推定分散の大きさを調
整する以外に、スケール６８を調整することによ
り、全てのビツトが割当てられるようにしてい
る。 従来のアルゴリズムは、本願発明に使用された
推定分散と同様な、大きさに対してビツトを割当
てるために存在していたと認められる。しかしな
がら、方程式や方法は非常に複雑で長いものであ
るため、それらは実時間で実行されない。そのよ
うなビツトを割当てるシステムの１つが、前述し
たSegalの論文に表されている。さらに、最適な
状態に及ばない結果を生み出すHaughやShortill
の方法を採用した、前述したCoxなどの文献のよ
うに、ビツトを割当てるのに必要な時間の長さを
克服するために、次善のアルゴリズムあるいは技
術を用いてビツトを割当てる試みがなされてい
た。 本願発明は、第３図と第５図を参照して前述し
た最適な方法で、全てのビツトを割当てる簡単で
効率的な方法を提供しようとするものである。 本願発明の高速データ圧縮ハードウエアを用い
た環境を示す簡単なブロツク図である第７図を参
照して説明する。線６９上の音声データを含むア
ナログデータは、Ａ／Ｄコンバータ７１によりデ
ジタル信号に変換され、96Kbpsで線７２上にデ
ジタルデータを出力している。フアーストイン・
フアーストアウト（FIFO）バツフア７３は、処
理のためにハードウエア・データ圧縮器７３に線
７４を通してデータのブロツクを出力している。
ハードウエア・データ圧縮器７５に向かう線７４
上のデータレートは、好ましくは96Kbpsである。
データがデータ圧縮器７５で処理された後、デー
タ圧縮比が１／４が希望されているとき、
16Kbpsで線７６のデータリンクに伝送される。
ビツトの割当て数が増加あるいは減少されて、処
理されるべきアナログデータの圧縮比が変更され
る。このシステムはアナログ情報と同様に、線７
７で示されたデジタル情報入力線からのデジタル
情報をも処理できる。データリンクを渡つて伝送
されたデータは、１秒当り16Kbpsで線７８より
受信され、ハードウエアの伸長器７９に入力され
る。伸長された出力は線８２を介してフアースト
イン・フアーストアウト・バツフア（FIFO）８
１に格納される。バツフア８１に記憶された情報
は96Kbpsで線８３に出力され、Ｄ／Ａコンバー
タ８４でデジタル信号からアナログ信号に変換さ
れ、線８５にアナログ信号で出力される。この信
号は線６９上の元の入力情報が伸長された複製物
である。このデータ圧縮器７５と伸長器７９はデ
ジタルデータあるいはアナログデータを処理でき
るため、出力線８６はデジタルデータの出力する
ために示されている。 第８図は第７図のデータ圧縮器７５の簡単な構
成を示すブロツク図で、次はこの図を参照して説
明する。データ入力線７４上のデジタルデータ
は、マルチプレクサ８７に入力され、線８８を介
してALU９１のバツフア８９に供給される。こ
の実施例のシステムは、４つの異なる電話線とし
て使用できる４つのデータ入力線７４と、１本の
データリンクラインにより伝送される情報を処理
できることが、マルチプレクサ８７により示され
ている。ALU９１とバツフア８９は、入力情報
のブロツクを受け取るようになつており、この入
力情報はバス９２を介して伝送され、保持レジス
タ９３からバス９５を介してメモリ９４に送られ
る。処理されるサンプルは処理される前に、まず
メモリ９４にデジタル情報で記憶される。アドレ
スジエネレータ９６はバス９７を介してメモリ９
４の情報をアクセスしてデジタルデータのサンプ
ルの複製を引出す。このデジタルデータは保持レ
ジスタ９３に伝送されて、ルツクアツプテーブル
９８に記憶された一定の値の情報を用いて、前述
した推定分散及び限界回帰データを計算するため
に、ALU９１で処理される。 こうして計算された推定分散は再び、その関連
するメモリアドレスとともに高速メモリ９４に記
憶され、高速のアクセス及び情報の処理を可能に
している。その処理された情報はALU９１、保
持レジスタ９３及び比較器９９を用いて並べ替え
られる。前述した計算の全ては制御ブロツク１０
２のプログラムメモリ部１０１にプログラムされ
ている。処理順序やタイミング制御は、第８図に
示された全てのブロツクにバス１０３を介して制
御情報やタイミング情報を出力している制御部１
０２の論理的な機能である。制御バス１０３上の
命令は136ビツトの制御ワードであり、このワー
ドによりデータ圧縮器７５の全ての部分を同時に
制御できる。制御部１０２がそのプログラムや、
処理順序及び適切なタイミング制御を行なうのに
必要な情報は、線１０４上のALU８６からの、
線１０５上の比較器９９からの及び線１０６上の
アドレスジエネレータ９６からのステータス情報
である。好適な実施例のデータ圧縮器７５では、
２つの部分からなる（bisection）アドレスジエ
ネレータ１０７を備えている。このジエネレータ
は第３図を参照して説明された前述のポインタシ
ステムで使用されないが、第５図のブロツク４７
で説明された好適な実施例のビツトマーカ割当て
システムで使用されている。 データ圧縮器７５では、データは一回で１つの
ブロツクに圧縮されて出力線１０８に送られ、マ
ルチプレクサ１０９を介して、データリンク７６
と同じデータ出力線１１１に伝送される。 次に、第７図と第８図に示された好適な実施例
のデータ圧縮器７５を詳細に示した第９図を参照
して説明する。 バツフアに記憶されたサンプル値は、線８８を
通りALU９１に供給され、そこでサンプルは整
数表現からデジタルサンプルの浮動小数点表現に
変換される。線１１３上の浮動小数点表現のサン
プルは、保持レジスタ９３Ｌの入力線１１２に供
給される。デジタル形式の浮動小数点表現は、線
９５を介して保持レジスタ９３から高速メモリ９
４に伝送され、連続したアドレスの順に格納され
る。全てのサンプルが高速メモリ９４に格納され
ると、線９５を介して高速メモリ９４から保持レ
ジスタ９３に伝送されるとき、比較器９９で個々
のサンプル毎に比較されてソートされる。制御部
１０２でなされて決定に基づいて、前述したよう
に、推定分散が減少する順に個々のサンプルが高
速メモリ９４に戻される。 ALU９１が前述したポインタ方法で動作して
いるときは、アドレスジエネレータ９６は線９７
上にアドレスを出力し、保持レジスタ９３を通し
てALU９１に供給されるメモリ９４からの推定
分散をアクセスすることができる。予め計算さ
れ、記憶されている累積利得因子は、線９７を介
してアドレスジエネレータ９６と、線１１５にル
ツクアツプテーブル９８へのアドレスを供給して
いるパイプラインレジスタ１１４でアクセスされ
る。ルツクアツプテーブル９８の定数は、線１１
６を介してバス９２Ｒに供給され、バス９２Ｒを
エネーブルにして、ALU９１の右側９１Ｒある
いは左側９１Ｌに供給される。ALU９１の左側
に供給されるときは、バス９２ＲはALUバツフ
ア１１７を通して、ALU９１Ｌに接続されてい
る左側のバス９２Ｌに接続される。累積利得Ｇが
乗算された分散の大きさは、前述した限界回帰値
となる。 比較される限界回帰は10個の値しかないので、
限界回帰の最高の順位はALUで計算されるが、
多くの数の比較が必要なときは比較器９９を用い
て計算しても良い。所定のポインタに対して最大
限界回帰値が求められると、それに関連した、ま
たアドレスジエネレータ９６に含まれたアドレス
が、前に説明したように次に最も低い推定分散値
のためにインクリメントされる。これにより、そ
のポインタの上のサンプルに１ビツトを効率よく
割当てることができる。ポインタを移動すること
による効果としては、ポインタアドレスによつて
規定された最高の限界回帰を有する要素あるいは
サンプルに１以上のビツトを割当てることができ
ることにある。システム７５の処理は第３図のブ
ロツク３７で行ない、周辺利得あるいは回帰は１
ビツトを受け取つたサンプルのために減少され
る。ポインタは次の最も低い推定分散に移動する
と、プログラムメモリ１０１の制御のもとに、プ
ロセツサ９１が全てのビツトが割当てられたかど
うかを判定する。割当てられていなければプログ
ラムは再びサブリストにおけるポインタのために
限界回帰Ｐ（ｂ，ｋ）を計算する。そして再び、
最大限界回帰を有するポインタのサンプルには１
ビツトが割当てられる。そのポインタは次のより
低い推定分散へ移動し、そのポインタに関連した
限界回帰は、新たに推定分散を指示したものを用
いて計算される。それから、全てのビツトが割当
てられたかどうかが決定される。最後のビツトを
受け取るサンプルに対応する更新されたポインタ
のためにのみ、限界回帰の計算がなされる。これ
は、他のポインタは依然同じ限界回帰を有してい
るためである。その計算は全てのビツトが割当て
られて、ビツトの割当てが完了するまで続けられ
る。ビツトの割当てが完了すると、高速メモリ９
４のデータは高速メモリの情報を保持レジスタ９
３に取出して、ALU９１で量子化動作を実行す
ることにより量子化される。量子化された情報は
サンプル毎或は要素毎に伝送され、伝送される情
報はALU９１の左側から書込み線１１３上に出
力される。情報が線１１３を介して線１１１上に
伝送される前に、浮動小数点表現がALU９１Ｌ
で整数表現に変換される。計算がALUの左側９
１Ｌで実行されるように説明してきたが、ALU
９１Ｒもまた実時間で情報のブロツクを処理する
ために計算を実行していることが理解されるであ
ろう。２つのALU９１Ｌと９１Ｒの任務の割当
ては、基本的にプログラムメモリ１０１の作用に
よるもので、これ以上の説明は不要であろう。 量子化計算が実行されるときは、最後のビツト
割当てが高速メモリ９４に記憶された後である。
入力データとビツト割当ては、線９５を介して
ALU９１に伝送される。ビツト割当てはルツク
アツプテーブル９８の定数をアドレスするアドレ
スとして使用される。この動作中、ALUは、線
１１９上にアドレスを出力し、ルツクアツプテー
ブル９８をアクセスするのに必要なアドレスを出
力するために使用されているバツフア１１７と１
１８とをアドレスしている。線１１９は制御部１
０２からのバス１２１に接続され、アドレスジエ
ネレータ９６にアドレスを出力している。 ALU９１で除算が実行されるときはいつも、
ALU９１の外部にある１対のルツクアツプテー
ブル１２２と１２３が、その処理を高速に行うた
めに備えられている。よつて、テーブル１２２か
らのルツクアツプ・データは指数を、テーブル１
２３からのルツクアツプ・データは仮数のために
使用される。ルツクアツプテーブル１２２と１２
３には、ALUにおける長い循環する計算を避け
る逆数がロードされていることが理解されるであ
ろう。 アドレスジエネレータ９６にはさらに、線９７
を介して高速ROM９４に供給されるアドレスの
アドレス動作をスピードアツプするためのパイプ
ラインレジスタ１２４やバツフアレジスタ１２５
への出力線９７が備えられている。 次に、第５図と第９図及び２分（bisection）
アドレスジエネレータ１０７を参照して説明する
第５図のブロツク４４で既に説明したように、参
照値を求めるための計算が行なわれる。マーカ値
は、その参照値と、マーカと参照値との間の予め
定められた比を基に計算される。マーカ値はビツ
トを割当てるために並べられたデータ内でそのマ
ーカを配置し、位置付けるために使用される。マ
ーカの配置はマーカ値を比較器９９にロードし、
その値と、２分アドレスジエネレータ１０７に関
連したアドレスジエネレータ９６によつて指示さ
れたアドレスの値と比較することにより行なわれ
る。全てのマーカが配置されると、予め定められ
たマーカ比と現在の参照値を用いて、全てのビツ
トが適正に割当てられたかを判定することが可能
になる。 ビツト割当てがあまりに高いと、制御プログラ
ムは新たな参照値を作成する。逆に、ビツト割当
てがあまりに低いと、より高い参照値が計算され
る。この処理は適正な数のビツトがマーカの位置
に割当てられてしまうまで繰返し実行される。
次々とより小さなステツプ、及び修正ループを繰
返して参照値を更新することにより、その処理に
よりマーカの最適なビツト配置に近付くことがで
き、こうして使用されるビツトが適正に割当てら
れる。 最適なビツト割当てが唯一なものでない場合、
唯一の解法が存在するビツトに対して最適なビツ
ト割当てが実行され、残りのビツトが同等に価値
のあるサンプルの間で任意に割当てられる。 ALU９１からの制御線１０４、比較器９９よ
りの制御線１０５及びアドレスジエネレータ９６
からの制御線１０６は、制御部１０２の選択ステ
ータス・ブロツク１２６に接続されている。制御
アドレスジエネレータ・バツフア１２７は、前述
したプログラムメモリ１０１により、アドレスジ
エネレータ９６に対してバス１２１上にアドレス
を出力する。プログラム制御バス１０３は好まし
くは136ビツトで、ほとんどのミニコンピユータ
や小規模のプロセツサにおいてみられるように、
ALU９１から作用されるプログラム以外で制御
される第９図の各ユニツトに接続されている。 実時間でのデータ圧縮を行なう好適な実施例
を、ポインタシステム形式と第２の好適な実施例
のマーカあるいは参照値システム形式で説明して
きたが、最適なビツト割当てを実現するのに必要
な時間の差は、400ビツトの場合はほとんどなく、
いずれの場合も同じようにサンプルに対して最適
にビツトが割当てられる。この実施例で使用され
た装置と同様にこの実施例のビツト割当てる方法
は、デジタルやアナログデータ・ブロツクにも適
用でき、30ms以内でデータ圧縮を実現できると
ともに、データ圧縮のために最適にビツトが割当
てられている間、圧縮されたデータをデジタル形
式で伝送することができる。その圧縮されたデー
タを伸長する受信装置は、線１１３あるいは線７
６上のデータがさらに、伝送されているサンプル
を復号するのに必要な情報を含んでいるため、高
度に簡素化されている。そして、システムは第９
図に示された回路よりも、より簡単になつてい
る。 この実施例では、適応変換符号化を用いて説明
してきたが、実時間でデータ圧縮を行なうのに必
要な速度が得られる重要な要素である。データ圧
縮のために最適にビツトを割当てを行なうハード
ウエアや方法を変更することなく、他の変換符号
化を用いても良い。 前述した方法は、音声あるいは会話データを
１／４あるいは１／２の圧縮するようになつてい
たが、同一の装置や方法により、他の好適な圧縮
比でデータ圧縮を行つてもよい。例えば、音声の
質が重要な要素でなく、大量の音声データを伝送
することが重要であるときは、音声データを粉失
することなく、圧縮比を１／８まで上げることが
できる。より高い圧縮比は、伝送される音声デー
タの質を低下させることにより実現できる。実時
間での処理が重要でない場合は、データの損失な
く圧縮比を最大Ｙ〜10まで実現できるような、他
の形式の損失のないデータ圧縮が利用できる。こ
のようにして、本願発明及びシステムより、より
速くより経済的に、より大きな容量の繰返しデジ
タルデータが伝送できる。しかしながら、本願発
明は、9.6Kbpsから32Kbpsの間のビツトレート
で商業的に利用できるデータリンクに実時間で伝
送できるように、音声およびモデム信号を圧縮で
きる既知のシステムに、最高の再生品位を提供す
るものである。