Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://patents.google.com/patent/JPS63281524A/en below:

JPS63281524A - Data compressing arithmetic encoding device

【発明の詳細な説明】 （産業上の利用分野） 本発明は、情報の伝送あるいは記録の際に情報に含まれ
る冗長度を取り除いて圧縮し、伝送時間や記憶容量を節
約する圧縮符号化装置に関するものである。Detailed Description of the Invention (Industrial Application Field) The present invention is a compression encoding device that removes redundancy contained in information and compresses it when transmitting or recording information, thereby saving transmission time and storage capacity. It is related to.

（従来の技術） 冗長データを圧縮する方法及び圧縮されたデータからも
との冗長データを復元する方法として従来一般によく知
られ利用されているものに、算術符号と呼ばれる符号を
用いる方法がある。算術符号のデータ圧縮器及び算術符
号のデータ復号器の詳細については、例えば米国のイン
ターナショナル・ビジネス・マシンズ・コーポレーショ
ン（Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｂｕｓｉｎｅｓｓ　
Ｍａｃｈｉｎｅｓ　Ｃｏｒｐｏｒａｔｉｏｎ）から１９
７６年に発行された論文誌アイビーエム・ジャーナル・
オブ・リサーチ・アンド・デベロップメント（ＩＢＭＪ
ｏｕｒｎａｌ　ｏｆ　Ｒｅ５ｅａｒｃｈ　ａｎｄ　Ｄｅ
ｖｅｌｏｐｍｅｎｔ）の第２０巻３号の１９８〜２０３
ページや、１９８４年に発行された同誌第２８巻２号の
１３５〜１４９ページや、米国のスタンフォード大学（
Ｓｔａｎｆｏｒｄ　Ｕｎｉｖｅｒｓｉｔｙ）で１９７６
年に発行されたリチャード・クラーク・パスコ（Ｒｉｃ
ｈａｒｄ　Ｃ１ａｒｋＰａｓｃｏ）による博士論文「ソ
ース・コーディング・アルコリズム・フォア・ファース
ト・データ・コンプレジョン（Ｓｏｕｒｃｅ　　ｃｏｄ
ｉｎｇ　　ａｌｇｏｒｉｔｈｍ　　ｆｏｒ　　ｆａｓｔ
　　ｄａｔａｃｏｍｐｒｅｓｓｉｏｎ月に詳しく述べら
れている。なお以下では算術符号のデータ圧縮器のこと
を単に算術符号器あるいは算術符号化装置と言い、算術
符号のデータ復号器のことを単に算術復号器あるいは算
術復号化装置と言う。(Prior Art) A method of compressing redundant data and restoring original redundant data from compressed data that has been well known and used in the past is a method that uses a code called an arithmetic code. For details on arithmetic code data compressors and arithmetic code data decoders, see, for example, International Business Machines Corporation of the United States.
Machines Corporation) to 19
IBM Journal published in 1976.
of Research and Development (IBMJ)
Our own of Re5earch and De
Volume 20, No. 3, 198-203 of
Pages 135-149 of Vol. 28, No. 2 of the same magazine published in 1984, and Stanford University in the United States (
Stanford University) in 1976
Richard Clarke Pasco (Ric
The doctoral dissertation "Source Coding Algorithm for First Data Complexion" by Hard C1arkPasco
ing algorithm for fast
Data compression is detailed in the following section. In the following, an arithmetic code data compressor is simply referred to as an arithmetic encoder or an arithmetic coding device, and an arithmetic code data decoder is simply referred to as an arithmetic decoder or an arithmetic decoding device.

これらの方法のうちデータを圧縮する方法について簡潔
に述べれば、信号系列すなわち情報ディジット列ｘ１ｓ
ｘ２＋・、・、ＸＮは、その冗長度に応じて長さの異な
る符号ディジット列’Ｎ１　、　Ｗ２．　＝・町に、例
えば次のようにして変換され、情報ディジット列の冗長
度が取り除かれる。Of these methods, to briefly describe the method for compressing data, a signal sequence, that is, an information digit string x1s
x2+·,·,XN are code digit strings 'N1, W2, . =・town, for example, as follows, and the redundancy of the information digit string is removed.

まずＦを予め決められた数直線上の区間（０以上１未満
とする）の小さい方の端の値（すなわち０）とし、Ｔを
その区間の輻（すなわち１）とする。次に以下の手順Ａ
Ｉ）〜Ａ５）を実行する。なお以下ではｚ＋−ｙはｘＧ
：ｙの値を代入することを意味するものとする。First, let F be the value at the smaller end (ie, 0) of a predetermined interval on a number line (between 0 and less than 1), and T be the convergence of that interval (ie, 1). Next, follow step A
Execute I) to A5). In addition, in the following, z+-y is xG
: means to substitute the value of y.

また演算はすべてｂ進法で行うものとする。It is also assumed that all operations are performed in the b-adic system.

ＡＩ）　ｉの値を１とする。AI) Set the value of i to 1.

Ａ２）　　第ｉ番目の情報ディジットをＸｉを入力する
。A2) Input the i-th information digit as Xi.

Ａ３）第ｉ番目の情報ディジットの出現確率ｑｉ（ｘｉ
）と累積出現確率Ｃ１（ｘｉ）＝Σｙ＜ｘｑｉ（ｙ）を
求める。A3) Appearance probability qi (xi
) and the cumulative appearance probability C1(xi)=Σy<xqi(y).

Ａ４）　　Ｆ４−Ｆ十〇、（ｘｓ）・ＴＴ＋−ｑｉ（ｘ
ｉ）・Ｔ とし、Ｔを予め決められた有効数字に桁で打ち切る。A4) F4-F〇, (xs)・TT+-qi(x
i) T , and truncate T to a predetermined significant figure.

Ａ５）　ｉ＜Ｎならｉの値を１増やしてＡ２）へ移る。A5) If i<N, increase the value of i by 1 and move on to A2).

ｉ＝Ｎなら終了。If i=N, end.

最後に、ＦとＴの最終値で決定される区間に含まれる実
数のうち、数値表現したときのディジット数が少ない実
数を選び、選ばれた実数の表現デイツプ）０．Ｗｌ、Ｗ
２”・・ｗｌ、の小数点以下の部分を符号ディジット”
Ｉｓ　”２”・・ｗＬのとして定める。上記手順ＡＩ）
〜Ａ５）に従えば符号語の長さＬは情報ディジット列の
長さＮより一般に小さくなってデータ圧縮できることが
前記文献に示されている。Finally, from among the real numbers included in the interval determined by the final values of F and T, a real number with the least number of digits when expressed numerically is selected, and the representation depth of the selected real number is 0. Wl, W
2"...wl, the part below the decimal point is the sign digit"
Is "2"...Define as wL. Above procedure AI)
~A5), the length L of the code word is generally smaller than the length N of the information digit string, and it is shown in the above-mentioned document that data can be compressed.

一方、データを復元する方法について簡潔に述べれば、
符号ディジット列Ｗｌ　、　Ｗ２．・・・ｔ”Ｌは例え
ば次のようにして変換され、もとの情報ディジット列”
１＞ｘ２・・・ＸＮが復元される。On the other hand, to briefly describe how to restore data:
Code digit string Wl, W2. ...t"L is converted as follows, for example, and the original information digit string"
1>x2...XN is restored.

まず、Ｗに０．ｗｌ、　ｗ２．−、　ＷＬを代入し、Ｓ
に１を代入する。次に以下の手順Ｂｌ）〜Ｂ５）を実行
する。なお以下ではｚ＋ｙはＸにｙの値を代入すること
を意味するものとする。また演算はすべてｂ進法で行う
ものとする。First, W is 0. wl, w2. −, substitute WL and S
Assign 1 to . Next, the following steps B1) to B5) are executed. Note that in the following, z+y means to substitute the value of y for X. It is also assumed that all operations are performed in the b-adic system.

Ｂｌ）　　ｉの値を１とする。Bl) Set the value of i to 1.

Ｂ２）　ＣｉＯ’）≦Ｗ／Ｓを満たすｙのうちで最大の
ディジットをｘｉとする。B2) Let xi be the largest digit among y that satisfies CiO')≦W/S.

Ｂ３）　ｘｉを復元された情報ディジットとして出力す
る。B3) Output xi as restored information digits.

Ｂ４）Ｗ４−Ｗ−Ｃ１（ｘｉ）・Ｓ Ｓ””ｑｉ（Ｘｉ）・Ｓ とし、Ｓを予め決められた有効数字に桁で打ち切る。B4) W4-W-C1(xi)・S S””qi(Xi)・S and truncate S to a predetermined significant figure.

Ｂ５）　　ｉ＜Ｎならｉの値を１増やしてＢ２）へ移る
。B5) If i<N, increase the value of i by 1 and move on to B2).

ｉ＝Ｎなら終了する。If i=N, the process ends.

上記手順にＢｌ）〜Ｂ５）に従えば符号ディジット列Ｗ
１．　Ｗ２＝ＷＬからもとの情報ディジット列ｘｂ　Ｘ
２”’ＸＮが誤りなく復元できることが前記文献に示さ
れている。算術符号は情報ディジットの出現確率さえ与
えられれば効率よく信号を圧縮する符号化法である。こ
のため符号器側と復号器側に機能の等しい予測器を具備
して、情報ディジットの出現確率を適応的に推定して効
率よく圧縮することが行われる。なお、圧縮効率を良く
するためには情報ディジットの長さを十分に長くする必
要がある。また、ここでは一般に情報ディジット単位に
符号化する場合について説明したが、実際の符号化装置
ではバイナリディジットすなわちビット単位で符号化を
行うことが多い。If you follow the above steps Bl) to B5), the code digit string W
1. W2=Original information digit string xb from WL
The above-mentioned literature shows that 2''' A predictor with equal functionality is installed on the side to adaptively estimate the probability of occurrence of information digits and compress them efficiently.In order to improve the compression efficiency, the length of the information digits must be set to a sufficient length. Furthermore, although the case where information is generally encoded in units of digits has been described here, in actual encoding devices, encoding is often performed in units of binary digits, that is, bits.

さて上記のようなデータの圧縮及びデータの復元を実行
するための算術符号器及び算術復号器は、例えば、米国
のインターナショナル・ビジネス・マシンズ・コーポレ
ーションの米国特許第４．１２２゜４４０号などに記さ
れているような加算・乗算などの算術演算回路を含む回
路で実現できる。Now, an arithmetic encoder and an arithmetic decoder for compressing data and restoring data as described above are described, for example, in US Pat. This can be realized with a circuit that includes arithmetic operation circuits such as addition and multiplication, as shown in the figure below.

（発明が解決しようとする問題点） しかしながら従来の方法では、情報ディジット列に対し
て符号化を行って符号ディジット列を送出している間は
制御ディジットを送ることが出来ないので、圧縮効率を
良くするために情報ディジット列の長さを十分に長くす
ると、制御ディジットを送れない期間も長くなってしま
うという欠点があった。(Problem to be Solved by the Invention) However, in the conventional method, the control digits cannot be sent while the information digit string is encoded and the coded digit string is sent out, so compression efficiency is reduced. If the length of the information digit string is made sufficiently long to improve the performance, there is a drawback that the period during which no control digits cannot be sent becomes longer.

ところが、応用によって符号化を行っている間でも制御
コードを緊急に送り出すことが必要になる。例えば文章
データと画像データが混在しているようなデータでは、
文章データと画像データとではデータの確率構造が異な
り、データが変わるとそれに応じて確率値の算出方法も
変更しなければならないため、復号器側の予測器に算出
方法切り替えのための制御ディジットを送る必要がある
。また、情報ディジット列の長さが予めわからない用途
では、復号器に情報ディジット列の切れ目を知らせるた
めの制御ディジットを符号化の途中に送出する必要があ
る。However, depending on the application, it may be necessary to send control codes urgently even while encoding is being performed. For example, in data where text data and image data are mixed,
Text data and image data have different probability structures, and when the data changes, the method of calculating the probability value must also be changed accordingly. Therefore, a control digit to switch the calculation method is added to the predictor on the decoder side. I need to send it. Furthermore, in applications where the length of the information digit string is not known in advance, it is necessary to send a control digit during encoding to notify the decoder of the break in the information digit string.

本発明は、符号化の途中でも制御ディジットを送出でき
るデータ圧縮算術符号化装置を提供しようとするもので
ある。The present invention aims to provide a data compression arithmetic encoding device that can send control digits even during encoding.

（問題を解決するための手段） 本発明は、順に入力さ、れてぐるディジットに応じて予
め決められた方法を用いて、数直線上の予め決められた
区間を順に変更してゆき、最終的に得られた該区間に含
まれる実数の数値表現を入力されたディジット列に対す
る符号ビット列として出力するデータ圧縮算術符号化装
置であって、情報ディジットと制御ディジットのそれぞ
れに異なる値のビットを付加して得られた拡大ディジッ
トを同一のラインから出力する混合器と、混合器の出力
するディジット列をビット列に変換するパラレルシリア
ル変換器と、混合器の出力するディジットのうち情報デ
ィジットに対応するディジットのみを出力する遮断器と
、遮断器の出力によって情報ディジットの出現確率値を
算出する予測器と、予め固定された確率値を出力する固
定確率発生器と、予測器の出力と固定確率発生器の出力
を切り替えて出力するセレクタと、セレクタの出力する
確率値に応じてパラレルシリアル変換器の出力ビット列
に対して算術符号化を実行する算術符号器を具備するこ
とによって、情報ディジットを圧縮すると同時に制御デ
ィジットを送出することを特徴とする。(Means for Solving the Problem) The present invention sequentially changes predetermined intervals on a number line using a predetermined method according to the input digits, and A data compression arithmetic coding device that outputs a numerical representation of a real number included in the interval obtained as a code bit string for an input digit string, and adds bits of different values to each of the information digits and control digits. a mixer that outputs the expanded digits obtained by the mixer from the same line, a parallel-to-serial converter that converts the digit string output from the mixer into a bit string, and a digit that corresponds to the information digit among the digits output from the mixer. a predictor that calculates the occurrence probability value of an information digit based on the output of the circuit breaker, a fixed probability generator that outputs a pre-fixed probability value, and a predictor output and fixed probability generator. , and an arithmetic encoder that performs arithmetic encoding on the output bit string of the parallel-to-serial converter according to the probability value output by the selector, thereby compressing information digits and simultaneously It is characterized by transmitting control digits.

（作用） 本発明では基本的には次のようにして符号化の途中でも
制御ディジットを送れるようにする。まず、情報ディジ
ットと制御ディジットにそれぞれ異なる値のビットを付
加して新しい拡大ディジットを構成する。すなわち、情
報ディジットに対して０を付加して拡大ディジットを構
成するのであれば、制御ディジットに対しては１を付加
して拡大ディジットを構成する。そして拡大ディジット
に対して符号化を実行する。このようにすれば情報ディ
ジット列に制御ディジットを埋め込んで送出しても、復
号器は付加されたビットの値を調べることによって情報
ディジットと制御ディジットとに分離できるので、元の
情報ディジットと制御ディジットを正しく復元できる。(Function) The present invention basically allows control digits to be sent even during encoding as follows. First, bits of different values are added to the information digit and the control digit to form a new extended digit. That is, if a 0 is added to the information digit to form an extended digit, a 1 is added to the control digit to form the extended digit. Encoding is then performed on the expanded digits. In this way, even if the control digits are embedded in the information digit string and transmitted, the decoder can separate the information digits and control digits by checking the value of the added bits, so the original information digits and control digits can be separated. can be restored correctly.

なお、符号器側と復号器側に適応的に情報ディジットの
出現確率を推定する予測器を備えている場合には、単に
拡大ディジット列に応じて予測を行っていると、符号化
の途中で送出される制御ディジットの数が多くなったと
きに予測器の内部の状態が撹乱されて予測の精度が低下
する。そこで本発明では、拡大ディジットが制御ディジ
ットに対応するものであれば予測器への供給を遮断して
、予測の精度を確保する。Note that if the encoder and decoder sides are equipped with a predictor that adaptively estimates the probability of occurrence of information digits, if the prediction is simply made according to the expanded digit string, there will be errors during encoding. When the number of transmitted control digits increases, the internal state of the predictor is disturbed and the accuracy of prediction decreases. Therefore, in the present invention, if the expanded digit corresponds to the control digit, the supply to the predictor is cut off to ensure prediction accuracy.

しかしながら、単にビットを付加して拡大ディジットを
構成していたのでは圧縮効率が低下してしまう。例えば
情報ディジットの長さが８ビットであれば拡大ディジッ
トの長さは９ビットとなり、１２．５％も長くなってし
まう。本発明では、次のようにして圧縮率の劣化を小さ
く抑える。以下では説明の便宜上、拡大された情報シン
ボルには“θ″が付加され制御コードには“１″が付加
されているものとする。なお、実際には制御ディジット
の長さは必ずしも情報ディジットの長さに等しくないが
、情報ディジットよりも短い場合には情報ディジットの
長さに拡大し、情報ビットよりも短い場合にはいくつか
に分割して送出するものとする。また、予測器が算術符
号に与える確率値の精度をＪビットとする。すると、確
率値の最小値は２−Ｊで最大値は１−２−Ｊである。本
発明では、１／２，２−Ｊ、１−２−Ｊの３通りの固定
確率を発生し、算術符号器が拡大ディジットの付加され
たビットを符号化するときには“１′”と“０”が出現
する確率としてそれぞれ２−Ｊ。However, if the extended digits are simply added with bits, the compression efficiency will decrease. For example, if the length of the information digit is 8 bits, the length of the expanded digit is 9 bits, which is 12.5% longer. In the present invention, deterioration in compression ratio is suppressed to a minimum in the following manner. In the following, for convenience of explanation, it is assumed that "θ" is added to the enlarged information symbol and "1" is added to the control code. Note that in reality, the length of the control digits is not necessarily equal to the length of the information digits, but it expands to the length of the information digits when it is shorter than the information digits, and into several when it is shorter than the information bits. It shall be sent in parts. Further, the accuracy of the probability value given by the predictor to the arithmetic code is assumed to be J bits. Then, the minimum value of the probability value is 2-J and the maximum value is 1-2-J. In the present invention, three fixed probabilities of 1/2, 2-J, and 1-2-J are generated, and when the arithmetic encoder encodes the bits to which the extended digit is added, "1'" and "0" are generated. The probability of `` appearing is 2-J, respectively.

１−２−Ｊを選び、制御ディジットに対応する拡大ディ
ジットのビットのうち付加ビット以外のビットを符号化
するときには“０９１と“１”が出現する確率としてそ
れぞれ１／２と１７２を選び、それ以外のときには予測
器の出力する確率値を選ぶ。ビットを付加することによ
る符号ビット列の長さの増加を前記文献に従って算出す
ると、情報ディジットに付加されたビットによる１ディ
ジット当りの符号ビット列の長さの増加は一１ｏｇ２（
１−２−Ｊ）ビットとなり、制御“　ディジットに付加
されたビットによる１ディジット当りの符号長の増加は
Ｊビットとなる。確率の精度をＪ＝８程度に選ぶと一１
ｏｇ２（１−２−’）＝５．６Ｘ１０−”となり、圧縮
率の劣化はほとんど無視できる。もっともＪ＝８のとき
には制御ディジットに付加されたビットに対して符号ビ
ット列が８ビットも長くなってしまうが、制御ディジッ
トはそれほど頻繁に送出されないので、全体としてはビ
ットを付加することによる圧縮効率の劣化はほとんど無
視できる。1-2-J, and when encoding the bits other than the additional bits among the bits of the extended digit corresponding to the control digit, select 1/2 and 172 as the probabilities that "091" and "1" will appear, respectively. In other cases, the probability value output by the predictor is selected.If the increase in the length of the code bit string due to the addition of bits is calculated according to the above literature, the length of the code bit string per digit due to the bits added to the information digit is The increase in is -1og2 (
1-2-J) bits, and the increase in the code length per digit due to the bits added to the control digits is J bits.If the accuracy of the probability is chosen to be about J = 8, -1
og2(1-2-')=5.6X10-'', and the deterioration in compression ratio can be almost ignored. However, when J=8, the code bit string is 8 bits longer than the bits added to the control digit. However, since the control digits are not sent very often, the overall deterioration in compression efficiency due to the addition of bits is almost negligible.

第１図に本発明の基本構成図を示す。図において情報デ
ィジットは入力端子１０１から、制御ディジットは入力
端子１０２からそれぞれ入力される。入力された情報デ
ィジットと制御ディジットには混合器１０３において、
それぞれ異なる値のビットが付加され、拡大ディジット
として同一のラインから出力されてゆく。拡大ディジッ
トはパラレルシリアル変換器１０８においてビット列に
変換された後、算術符号器１０９において符号化される
。算術符号器１０９が符号化を行って得られたビット列
は出力端子１１０から順に出力されてゆく。拡大ディジ
ットは遮断器１０４を介して予測器１０５にも供給され
ている。FIG. 1 shows a basic configuration diagram of the present invention. In the figure, information digits are input from input terminal 101, and control digits are input from input terminal 102, respectively. The input information digits and control digits are mixed in a mixer 103.
Bits of different values are added and output from the same line as enlarged digits. The expanded digit is converted into a bit string by a parallel-to-serial converter 108 and then encoded by an arithmetic encoder 109. The bit string obtained by encoding by the arithmetic encoder 109 is sequentially output from the output terminal 110. The magnified digits are also supplied to predictor 105 via circuit breaker 104 .

遮断器１０４は拡大ディジットに付加されたビットの値
によって拡大ディジットが情報ディジットと制御ディジ
ットのどちらかに対応する識別し、拡大ディジットが情
報ディジットに対応する場合にだけ情報ディジットを予
測器１０５に供給する。予測器１０５は次に入力される
情報ディジットのそれぞれのビットの出現確率値を算出
し、確率値をセレクタ１０７を介して算術符号器１０９
に供給する。算術符号器１０９に確率値を供給するのは
予測器１０５だけでなく、固定確率発生器１０６もセレ
クタ１０７を介して確率値を供給している。セレクタ１
０７は拡大ディジットのうち算術符号器１０９が情報デ
ィジットに対応するビットを符号化しているときには予
測器の出力を選び、それ以外の場合は固定確率発生器を
選択する。固定確率値の選び方はすでに述べたとおりで
ある。The circuit breaker 104 identifies whether the extended digit corresponds to either an information digit or a control digit based on the value of the bit added to the extended digit, and supplies the information digit to the predictor 105 only when the extended digit corresponds to an information digit. do. The predictor 105 calculates the appearance probability value of each bit of the next input information digit, and sends the probability value to the arithmetic encoder 109 via the selector 107.
supply to. It is not only the predictor 105 that supplies probability values to the arithmetic encoder 109 , but also the fixed probability generator 106 that supplies probability values via the selector 107 . Selector 1
07 selects the output of the predictor when the arithmetic encoder 109 encodes the bit corresponding to the information digit among the expanded digits, and selects the fixed probability generator otherwise. The method of selecting the fixed probability value has already been described.

（実施例） 第２図に本発明の一実施例を示す。図において第１図と
同一の機能を有するブロックには同二の番号を付しであ
る。図において長さ８ビットの情報ディジットと制御デ
ィジットはそれぞれ入力端子２０１゜２０３から入力さ
れる。入力された情報ディジットには端子２０５から供
給されるビット“θ′′が、制御ディジットには端子２
０６から供給されるビット“１”が付加されて混合器１
０３内部のバッファ２０７．２０８にそれぞれ入力され
る。入力端子２０２．２０４には、それぞれバッファ２
０７．２０８に情報ディジットと制御ディジットとを入
力するためのクロックが入力され、入力端子２０２．２
０４にクロックパルスが入ると、拡大された情報ディジ
ットと制御ディジットとがバッファ２０７、２０８にそ
れぞれ入力される。バッファ２０７゜２０８は一番最初
に入力されたディジットが一番最初に出力されるＦＩＦ
Ｏ型のバッファである。バッファ２０７、２０８は拡大
ディジットだけでなく、バッファ内部にデータが保持さ
れているかどうかを示す信号もセレクタ２０９に供給し
ており、セレクタ２０９はこの信号にもとづいてバッフ
ァ２０７．２０８のうちデータが保持されているバッフ
ァの出力を読みだし、読み出された拡大ディジットをセ
レクタ２０９の出力とする。なお、両方のバッファにデ
ータがある場合にはバッファ２０７の出力を優先的に読
み出すものとする。セレクタ２０９からは選択した拡大
ディジットだけでなく拡大ディジットを保持させるため
のクロックパルスも出力されており、これらは遮断器１
０４とパラレルシリアル変換器１０８に供給される。(Example) FIG. 2 shows an example of the present invention. In the figure, blocks having the same functions as those in FIG. 1 are given the same numbers. In the figure, information digits and control digits each having a length of 8 bits are input from input terminals 201 and 203, respectively. The input information digit has the bit "θ'' supplied from terminal 205, and the control digit has the bit "θ'' supplied from terminal 205.
The bit “1” supplied from 06 is added to mixer 1.
The signals are respectively input to buffers 207 and 208 inside 03. Input terminals 202 and 204 each have a buffer 2.
A clock for inputting information digits and control digits is input to input terminal 202.2.
When a clock pulse is received at 04, the expanded information digits and control digits are input to buffers 207 and 208, respectively. Buffers 207 and 208 are FIFs in which the first input digit is output first.
It is an O type buffer. The buffers 207 and 208 supply not only the expanded digit but also a signal indicating whether or not data is held inside the buffer to the selector 209. Based on this signal, the selector 209 determines which of the buffers 207 and 208 the data is held. The output of the buffer being read out is read out, and the read expanded digit is set as the output of the selector 209. Note that when there is data in both buffers, the output of the buffer 207 is read out preferentially. The selector 209 outputs not only the selected expanded digit but also a clock pulse for holding the expanded digit, and these are output to the circuit breaker 1.
04 and the parallel/serial converter 108.

遮断器１０４では論理積回路２２０によって、セレクタ
２０９から出力される拡大ディジットの付加ビットと拡
大ディジットを保持するためのクロックパルスとの論理
積をとり、その出力を予測器１０５の入力クロック端子
に供給することによって、拡大ディジットが制御ディジ
ットに対応するときには予測器１０５にディジットが保
持されないようにしている。In the circuit breaker 104, an AND circuit 220 performs an AND operation between the additional bit of the expanded digit outputted from the selector 209 and a clock pulse for holding the expanded digit, and supplies the output to the input clock terminal of the predictor 105. This prevents the predictor 105 from retaining the digits when the expansion digits correspond to control digits.

パラレルシリアル変換器１０８ではセレクタ２０９から
供給されるクロックパルスで拡大ディジットを保持し、
これをパラレルシリアル変換して算術符号器１０９に供
給する。パラレルシリアル変換器１０８はパラレルシリ
アル変換を行うだけでなく、出力ビットを保持させるた
めのクロックパルスと、出力したビットが拡大ディジッ
トの何醤目かを示す位置情報も出力される。位置情報の
初期値は０で、拡大ディジットのうち付加されたビット
が一番最初に出力される。The parallel-to-serial converter 108 holds the enlarged digit with the clock pulse supplied from the selector 209,
This is subjected to parallel-to-serial conversion and supplied to an arithmetic encoder 109. The parallel-to-serial converter 108 not only performs parallel-to-serial conversion, but also outputs clock pulses for holding output bits and positional information indicating the position of the enlarged digit of the output bit. The initial value of the position information is 0, and the added bit of the expanded digit is output first.

セレクタ１０７では、否定論理和回路２３０によってパ
ラレルシリアル変換器１０８から供給される４ビットの
位置情報の否定論理和をとって、その結果をセレクタ２
２８．２２９へ出力している。否定論理和回路２３０の
出力が１すなわちパラレルシリアル変換器から出力され
たビットが付加ビットのときにはセレクタ２２８と２２
９はそれぞれ端子２２２と２２３から供給される値２−
Ｊと１−２−Ｊ（すなわち８ビットの二進数小数表示で
０．０００００００１と０．１１１１１１１１を選んで
算術符号器に供給し、否定論理和回路２３０の出力が０
のときにはそれぞれセレクタ２２５．２２６の出力を選
んで算術符号器に供給する。否定論理和回路２３０の出
力は論理積弁２２７にも供給されており、シリアルパラ
レル変換器１０８へ供給されるクロックパルスとの論理
積がとられた後に、フリップフロップ２・２４のクロッ
ク信号端子に入力されている。フリップ７０ツブ２２４
のデータ入力はシリアルパラレル変換器１０８への入力
ビットで、クロック信号端子にクロックパルスが入ると
データ入力を保持してその値を出力する。否定論理和回
路２３０の出力はシリアルパラレル変換器１０８が付加
ビットを出力しているときにのみ１であるから、フリッ
プ７０ツブ２２４は付加ビットの値を保持することにな
る。フリップ７０ツブ２２４の出力はセレクタ２２５．
２２６に供給されており、フリップフロップ２２４の出
力が０のときにはセレクタ２２５と２２６は端子２２１
から供給される値０．５（すなわち８ビットの二進小数
表示で０．１０００００００）を選んでそれぞれセレク
タ２２８と２２９に供給し、フリップフロップ２２４の
出力が１のときには予測器１１５から供給される確率値
を選んでそれぞれセレクタ２２８と２２９に供給する。In the selector 107, a NOR circuit 230 performs a NOR operation on the 4-bit position information supplied from the parallel-to-serial converter 108, and the result is sent to the selector 2.
It is output to 28.229. When the output of the NOR circuit 230 is 1, that is, the bit output from the parallel-serial converter is an additional bit, the selectors 228 and 22
9 are the values 2- supplied from terminals 222 and 223, respectively.
J and 1-2-J (that is, 0.00000001 and 0.11111111 in 8-bit binary decimal notation are selected and supplied to the arithmetic encoder, and the output of the NOR circuit 230 is 0.
When , the outputs of the selectors 225 and 226 are selected and supplied to the arithmetic encoder. The output of the NOR circuit 230 is also supplied to the AND valve 227, and after being ANDed with the clock pulse supplied to the serial-parallel converter 108, the output is applied to the clock signal terminals of the flip-flops 2 and 24. It has been entered. flip 70 tube 224
The data input is an input bit to the serial-parallel converter 108, and when a clock pulse is input to the clock signal terminal, the data input is held and its value is output. Since the output of the NOR circuit 230 is 1 only when the serial-parallel converter 108 is outputting the additional bit, the flip 70 tube 224 holds the value of the additional bit. The output of the flip 70 knob 224 is sent to the selector 225.
226, and when the output of the flip-flop 224 is 0, the selectors 225 and 226 are connected to the terminal 221.
The value 0.5 (i.e. 0.10000000 in 8-bit binary decimal notation) supplied from The probability values are selected and supplied to selectors 228 and 229, respectively.

セレクタ２２５と２２８は０の発生確率を操作し、セレ
クタ２２６と２２９は１の発生確率を操作しているわけ
である。Selectors 225 and 228 operate on the probability of occurrence of 0, and selectors 226 and 229 operate on the probability of occurrence of 1.

（発明の効果） 以上述べてきたように、本発明に従えば従来のデータ算
術圧縮符号化装置と異なり、符号化の途中でも制御ディ
ジットを送出できるデータ圧縮算術符号化装置が容易に
構成できる。しかも本実施例で示したように簡単な回路
で構成できるから高速なデータ伝送システムやデータ記
憶装置にも対応できる。(Effects of the Invention) As described above, according to the present invention, unlike conventional data arithmetic compression encoding devices, it is possible to easily construct a data compression arithmetic encoding device that can send control digits even during encoding. Moreover, as shown in this embodiment, since it can be configured with a simple circuit, it can be applied to high-speed data transmission systems and data storage devices.

従って本発明が、今後の高速ディジタル通信回路網の展
開や大容量記憶装置の普及において、効率向上や性能向
上という点で効果を発揮できることは明らかである。Therefore, it is clear that the present invention can be effective in improving efficiency and performance in the future development of high-speed digital communication networks and the widespread use of mass storage devices.

第１図は本発明の基本構成図、第２図は本発明の一実施
例を示す図である。 １０１、１０２・・・出力端子、１０３・・・混合器１
０４・・・遮断器、１０５・・・予測器１０６・・・固
定確率発生器、１０７・・・セレクタ１０８・・・パラ
レルシリアル変換器 １０９・・・算術符号器、１１０・・・出力端子２０７
、２０８・・・バッファ、２０９・・・セレクタ２２５
、２２６．２２８．２２９・・・セレクタ第　１　　回FIG. 1 is a basic configuration diagram of the present invention, and FIG. 2 is a diagram showing an embodiment of the present invention. 101, 102... Output terminal, 103... Mixer 1
04... Breaker, 105... Predictor 106... Fixed probability generator, 107... Selector 108... Parallel-serial converter 109... Arithmetic encoder, 110... Output terminal 207
, 208...Buffer, 209...Selector 225
, 226.228.229...Selector 1st

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4