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

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

JPS63314918A - System for preventing carrying propagation in arithmetic coding

【発明の詳細な説明】 （発明の技術分野） 本発明は、画像の符号化やデータ伝送などのデータ圧縮
符号として用いられる算術符号化に係わり、特に圧縮デ
ータのデータ伝送及びメモリ領域への移動をリアルタイ
ムで可能とする算術符号化における桁上がり伝搬防止方
式に関する。Detailed Description of the Invention (Technical Field of the Invention) The present invention relates to arithmetic coding used as a data compression code for image coding and data transmission, and in particular to data transmission of compressed data and movement of compressed data to a memory area. This paper relates to a carry propagation prevention method in arithmetic coding that enables real-time processing.

（従来技術とその問題点） 算術符号は、エリアスによる符号化法がリッサネン（Ｒ
ｉｓｓａｎｅｎ）により一般化されたもので、〔０゜１
〕区間をデータシンボルの生起確率に応じて順次分割し
ていき、１つのシンボル列にある部分区間を対応させる
方法である。(Prior art and its problems) For arithmetic codes, the coding method by Elias is based on Risssenen (R
It was generalized by [0゜1
] This is a method in which an interval is sequentially divided according to the probability of occurrence of data symbols, and partial intervals in one symbol string are made to correspond.

従来、高い情報源を圧縮して伝送する符号化方式の代表
例として、出現確率の高い（又は低い）ものに対して短
い（又は長い）ビットを割り当てるハフマン符号がある
。第１図はハフマン符号と算術符号とを用いた場合にお
ける量子化ステップサイズ対符号化効率の特性を示した
ものである。Conventionally, a typical example of a coding method for compressing and transmitting high information sources is a Huffman code that allocates short (or long) bits to items with high (or low) occurrence probabilities. FIG. 1 shows the characteristics of quantization step size versus coding efficiency when Huffman codes and arithmetic codes are used.

同図はフィールド内前置予測、線形量子化器を用い、こ
れら符号化データより得られる量子化代表値に対して算
術符号化及びハフマン符号化を行ったものである。同図
から明らかなように、算術符号は量子化ステップサイズ
に関係なくほぼ一定の高符号化率を有している。従って
、近年は算術符号を用いてデータを圧縮する技術が注目
を浴びている。In the figure, arithmetic coding and Huffman coding are performed on quantized representative values obtained from these encoded data using intra-field pre-prediction and a linear quantizer. As is clear from the figure, the arithmetic code has a nearly constant high coding rate regardless of the quantization step size. Therefore, in recent years, techniques for compressing data using arithmetic codes have been attracting attention.

算術符号として、３値情報源の場合を例に取り説明を行
う。算術符号において、符号化系列は大きさが“′０′
”と“１′の間の２進小数、即ち、最左端に小数点が置
かれた２進数と見なされる。符号化は、以下に示す繰り
返し演算により行われる。As an arithmetic code, an explanation will be given using a ternary information source as an example. In arithmetic codes, the coded sequence has a size of "'0"
” and “1', ie, a binary number with the decimal point placed at the leftmost end. Encoding is performed by iterative calculations shown below.

アルファベラ）Ｓ＝　（０，１，２）の各シンボルＫ　
（＝０．１．２）がストリングＳの次のシンボルとなり
、ＳＫを生成するとき、そのＫに対し、オージエント被
加算数と言われるＡ　（ＳＫ）項を、シンボル系列であ
るストリングＳの符号Ｃ（Ｓ）に加えることにより、符
号化が行われる。ここでオージエン）Ａ（ＳＫ）は、（
２）弐のように、シンボルの出現確率に応じてＡ　（Ｓ
）が分割されたものである。符号化は、例えばシンボル
に＝０．１．２なる場合（３）式のように行われる。こ
こでＡ　（Ｓ）とＣ（Ｋ）の初期値をＡ　（ＮＵＬＬ）
　＝　１　　　　　　　−−−−−−−−−−−−−−
−−　（１）Ｃ（ＮＵＬＬ）　＝　０ とするとき、符号化は Ａ（Ｓに）　＝Ａ（Ｓ）　＊　Ｐ（Ｋ）　　　　　Ｋ≠
Ｏ−−−−−−−１２）Ｃ（ＳＫ）　＝Ｃ（Ｓ）　　　
　　　　　Ｋ　＝　０により行われる。Alphabella) S = Each symbol K of (0, 1, 2)
(=0.1.2) becomes the next symbol of the string S, and when generating SK, the term A (SK), which is called the argent addend, is added to the code of the string S, which is a symbol sequence. Encoding is performed by adding to C(S). Here, A (SK) is (
2) Like 2, A (S
) is divided. For example, when the symbol =0.1.2, encoding is performed as shown in equation (3). Here, the initial values of A (S) and C (K) are set to A (NULL)
= 1 −−−−−−−−−−−−−−
-- (1) When C(NULL) = 0, the encoding is A(S) = A(S) * P(K) K≠
O---------12) C(SK) = C(S)
This is done with K = 0.

符号化の実現のために、以下の手法が必要になる。In order to realize encoding, the following method is required.

（１）無限精度の乗算を避けるため有効桁数を一定桁数
に制限し、シンボルの出現確率Ｐを近似的に計算する。(1) In order to avoid multiplication with infinite precision, the number of effective digits is limited to a certain number, and the probability of symbol appearance P is approximately calculated.

そしてこのＰに対し２のべき乗近似を行い、符号化テー
ブル（ＳＫＥＷ）を作成し、乗算をシフト演算に置き換
える。Then, a power of 2 approximation is performed on this P to create an encoding table (SKEW) and replace the multiplication with a shift operation.

（２）　Ａ（Ｓ）の領域分割が進むに従って発生する上
位の連続する“０゛ビツトをシフティング法になる左シ
フトにより取り除く。(2) As the region division of A(S) progresses, the upper consecutive "0" bits that occur are removed by left shifting, which is a shifting method.

また、復号化は次のようにして行われる。いま、シンボ
ル系列であるストリングＳまですでに復号されているも
のとする。系列ＳＫのシンボルにはＣ（ＳＫ）　−Ｃ（
Ｓ）　＜Ａ（Ｓｏ）　　　　　　　　Ｋ　＝　Ｏ（４）
Ｃ（ＳＫ）−Ｃ（Ｓ）＜Ａ（Ｓｏ）＋Ａ（ＳＬ）　　Ｋ
＝１Ｃ（ＳＫ）　−Ｃ（Ｓ）　＜Ａ（Ｓｏ）　＋Ａ（Ｓ
ｔ）　＋Ａ（Ｓ２）　　Ｋ　＝　２なる関係で復号され
る。Moreover, decoding is performed as follows. It is now assumed that string S, which is a symbol sequence, has already been decoded. The symbols of series SK are C(SK) −C(
S) <A(So) K = O(4)
C(SK)-C(S)<A(So)+A(SL) K
=1C(SK) -C(S) <A(So) +A(S
t) +A(S2) K = 2.

次に必要なことは、実用上の観点からＡ（Ｓ’の値を制
限することである。このため、（１）式の加算は有限長
のレジスタで行われればならず、例えば高々Ｗ桁の有意
な浮動小数２進デジツトをもつものとなる。ここで、最
初に符号化されたものが、最初に復号されるＦＩＦＯ（
Ｆｉｒｓｔ　ｉｎ　Ｆｉｒｓｔ　ｏｕｔ）型の場合には
、Ａ　（Ｓ）はストリングの右端に加えられるため、多
くの桁を飛び越す桁上がりは正常に復号を行う上で好ま
しくない。算術符号は、符号化された系列の各部が符号
語に分けられるハフマン符号などと異なり、情報源系列
全体を１つの符号語に符号化してしまうため、１変復号
エラーが生ずると、それ以後の復号は完全に不可能とな
る。このため、Ｃ（Ｓ）の−足指以上の桁上がりを完全
に防止することが必要不可欠になる。What is next necessary is to limit the value of A(S' from a practical point of view. For this reason, the addition in equation (1) must be performed in a finite-length register, for example, at most W digits. significant floating point binary digits, where the first encoded is the first decoded FIFO (
In the case of the first in first out) type, A (S) is added to the right end of the string, so a carry that skips many digits is not desirable for normal decoding. Unlike Huffman codes, in which each part of the encoded sequence is divided into codewords, arithmetic codes encode the entire information source sequence into one codeword, so if a one-change decoding error occurs, subsequent Decryption becomes completely impossible. For this reason, it is essential to completely prevent C(S) from carrying beyond the minus toe.

第２図に、従来の算術符号化方式を用いた符号　　。Figure 2 shows a code using the conventional arithmetic coding method.

化部のブロックダイヤグラムを示す。符号Ｃ（Ｓ）を、
直接算術演算する最下位Ｗビットの算術演算レジスタ（
以下「Ｗレジスタ」と称する）、それに続くｖビットの
桁上がり監視レジスタ（以下「Ｖレジスタ」と称する）
、Ｗ＋Ｖビットより上位のバッファメモリとなる伝送用
バンファレジスタ（以下「Ｍレジスタ」と称する）の３
つの部分に分けることができる。符号Ｃ（Ｓ）とＡ　（
Ｓ）は、図の様な位置関係になる。演算は、長さＷビッ
トのＷレジスタ上で行い、それ以下の桁は切り捨てるこ
ととする。A block diagram of the conversion section is shown. The code C(S) is
The lowest W bit arithmetic operation register (
(hereinafter referred to as the "W register"), followed by the v-bit carry monitoring register (hereinafter referred to as the "V register")
, 3 of the transmission buffer registers (hereinafter referred to as "M registers") which serve as buffer memories above the W+V bits.
It can be divided into two parts. Codes C(S) and A (
S) has a positional relationship as shown in the figure. The calculation is performed on a W register with a length of W bits, and digits below that are truncated.

また、Ａ　（Ｓ）の分割が進むに従って、上位桁に“０
′°が連続するようになるが、左シフトすることにより
この部分を演算の対象から外す。これを、シフト処理と
呼ぶ。図中、１１はオージェントの累積和を蓄える累積
和蓄積レジスタ（以下、「Ａレジスタ」と称す）　、１
２．１３．１４は符号Ｃのためのレジスタであり、１２
はＡレジスタ１１と加算処理を行うためのＷレジスタ、
１３は連続°°１°′ビットを監視するための桁上がり
監視用レジスタである■レジスタ、１４は伝送用バッフ
ァメモリとなるＭレジスタを示す。又、１５は入力シン
ボルを蓄えるＡＧレジスタで、１６は入力シンボルに対
し符号化テーブル（ＳＫＥＷ）の値のだけビットシフト
されたオージェントを蓄えるＳＦレジスタ、１７はＳＦ
レジスタ１６で作成されたオージェントよりオージエン
トの累積和を作り蓄えられる３Ｍレジスタである。Also, as the division of A (S) progresses, “0” is added to the upper digits.
′° becomes continuous, but by shifting to the left, this part is removed from the calculation target. This is called shift processing. In the figure, 11 is a cumulative sum accumulation register (hereinafter referred to as "A register") that stores the cumulative sum of agents.
2.13.14 is a register for code C, 12
is the A register 11 and the W register for performing addition processing,
The reference numeral 13 indicates a register (1) which is a carry monitoring register for monitoring continuous °°1°' bits, and the reference numeral 14 indicates an M register which serves as a transmission buffer memory. Further, 15 is an AG register that stores input symbols, 16 is an SF register that stores an agent that is bit-shifted by the value of the encoding table (SKEW) with respect to the input symbol, and 17 is an SF register.
This is a 3M register that can create and store the cumulative sum of agents from the agents created in register 16.

第２図で、１つの入力シンボルを符号化する為の手順は
、以下のようになる。In FIG. 2, the procedure for encoding one input symbol is as follows.

（１）人力シンボルごとに、逐次ＡＧレジスタ１５、Ａ
Ｆレジスタ１６及び３Ｍレジスタ１７よりオージェント
の累積和が作られる。(1) For each human symbol, the AG register 15, A
A cumulative sum of agents is created from the F register 16 and the 3M register 17.

（２）Ａレジスタ１１のオージエントの累積和にＷレジ
スタ１２が加算される。このとき、もし桁上がりがあれ
ば後述する（４）項の処理を行う。(2) The W register 12 is added to the cumulative sum of the audience in the A register 11. At this time, if there is a carry, the process in section (4) described later is performed.

（３）オージエントの正規化を行うため、ＡＧレジスタ
１５のオージェント及びＷレジスタ１２．　　Ｖレジス
タ１３９Ｍレジスタ１４の符号の左へのシフト処理を行
う。(3) In order to normalize the augent, the augent in the AG register 15 and the augent in the W register 12. V register 139 performs processing to shift the sign of M register 14 to the left.

（４）■レジスタ１３のレジスタ内において、連続する
“ビ′ランの桁上がり監視を行い、■レジスタ１３内に
おいて前回にビット・スタッフインク処理により挿入し
た制御信号の位置と異なり、かつ、連続“１”ランが検
出できれば、新たに制御信号を連続“ｌ”ランの後に制
御信号を挿入する。(4) ■In the register 13, carry-over of consecutive "bi'runs" is monitored. If a 1" run is detected, a new control signal is inserted after the continuous "1" run.

（５）伝送用バッファであるＭレジスタ１４より、伝送
路又はメモリに符号化データが送られる。(5) Encoded data is sent from the M register 14, which is a transmission buffer, to a transmission path or memory.

ここで、桁上がりの伝搬を調べるため、■レジスタ１３
に入って（るビットは、 （Ａ）　　レジスタ１１とＷレジスタ１２の内容を加算
することによる桁上がりビット、 （Ｂ）　Ｗレジスタ１２における内容を左シフト処理す
ることによるビット の２種類に分けられる。桁上がり伝搬は、上記（Ａ）と
（Ｂ）の２種類ビットに対し、桁上がり監視レジスタで
ある■レジスタ１３内で必ず抑えられなければならない
。Here, in order to investigate the propagation of carry, ■Register 13
The bits that enter () can be divided into two types: (A) carry bits resulting from adding the contents of register 11 and W register 12, and (B) bits resulting from left-shifting the contents of register 12. Carry propagation must be suppressed in the (1) register 13, which is a carry monitoring register, for the above two types of bits (A) and (B).

はじめに、従来の桁上がり防止方式について説明する。First, a conventional carry prevention method will be explained.

これまで知られている技術として、桁上がり防止方式の
ために、制御信号を符号化系列に挿入するビット・スタ
ッフインク処理方法が知られている。以下に、ビット・
スタッフインクの２つの方法を示す。As a technique known so far, a bit stuff ink processing method is known in which a control signal is inserted into a coded sequence for a carry prevention method. Below is a bit
Two methods of staff ink are shown.

（１）■レジスタ１３の全ビットが“１”ビットとなる
ときに限り、レジスタ１３内のビットをシフトアップし
最下位ビット（ＬＳＢ）に制御信号として“０゛°ビツ
トを挿入する方法。(1) ■ A method of shifting up the bits in the register 13 and inserting a "0° bit" as a control signal into the least significant bit (LSB) only when all bits in the register 13 become "1" bits.

（２）上記（１）項の操作に加え、桁上がりにより■レ
ジスタ１３のＭレジスタ１４にまたがって監視レジスタ
製分の連続“１゛ランが発生した場合に関しても、連続
“１°゛ランの最下位に制御信号として“°０°′ビッ
トを挿入する方法。(2) In addition to the operation in item (1) above, in the case where a continuous "1" run of monitoring register division occurs across the M register 14 of the register 13 due to a carry, continuous "1" runs of A method of inserting the “°0°” bit as a control signal at the lowest position.

しかし、この従来の方法では、前述した桁上がりビット
としてシフト処理されたビットの双方に対して■レジス
タ１３内でかならずしも押さえられるとは限らない。上
述の処理例を方法（１）の場合は表１に、方法（２）の
場合は表に示す。表１及び表２の条件は、Ｖ＝Ｗ＝４ビ
ット、シンボルが、Ｋ＝０．１．２の３値情報源とする
。However, in this conventional method, both of the bits shifted as the carry bits described above are not necessarily held in the register 13. Examples of the above processing are shown in Table 1 for method (1) and in Table 1 for method (2). The conditions in Tables 1 and 2 are for a ternary information source with V=W=4 bits and symbols K=0.1.2.

表　　　　１ 表　　　　２ 表１は上述（Ａ）なる項の桁上がりにより、■レジスタ
１３とＭレジスタ１４にまたがって監視レジスタ製分の
連続“１゛′ランが発生するとき、制御信号が挿入され
ない例を示したものである。このとき受信側の復号部で
は、ビット・スタ・ンフイング処理により挿入された制
御信号を考慮して処理を行うため、復号エラーが生ずる
。表２を説明する。Table 1 Table 2 Table 1 shows an example in which the control signal is not inserted when a continuous "1'" run of monitoring register division occurs across registers 13 and M registers 14 due to the carry of term (A) mentioned above. At this time, the decoding section on the receiving side performs processing taking into consideration the control signal inserted by the bit stuffing process, so a decoding error occurs.Table 2 will be explained.

復号エラーに陥るときの、復号部における処理手順を、
以下のステップにより示す。The processing procedure in the decoder when a decoding error occurs is as follows:
This is illustrated by the following steps.

（Ａ）復号部のバッファメモリより読み込まれたビット
が、送信側の符号化部の監視レジスタ（■レジスタ１３
）製分連続して°“１゛ランとなる。(A) The bits read from the buffer memory of the decoding unit are stored in the monitoring register (■ register 13) of the encoding unit on the sending side.
) Continuously refining the product to make a 1-run run.

（Ｂ）ビット・スタッフインクにより、制御信号が挿入
されたと検知し、バッファメモリから１ビツトの２進符
号が読み込まれ、復号部の演算レジスタ（以後ｒＷＦレ
ジスタｊと称す）に加算される。(B) The bit stuff ink detects that a control signal has been inserted, reads a 1-bit binary code from the buffer memory, and adds it to the arithmetic register (hereinafter referred to as rWF register j) of the decoder.

（Ｃ）上記（Ｂ）で読み込んだビットが゛１パならば、
ビットスタッフィングの処理が連続して行われたと判断
し、さらにバッファメモリから１ビツトが読み込まれＷ
Ｆレジスタに加算される。(C) If the bit read in (B) above is ゛1pa, then
It is determined that bit stuffing processing has been performed continuously, and one bit is read from the buffer memory and W
Added to F register.

復号側では、送信側の処理手順に関わらず、常にビット
・スタッフインク処理が行われていると判断する。とこ
ろが送信側では、ビット・スタッフインク処理により挿
入される制御信号が連続する過程において、１回目と２
回目のビット・スタッフインク処理の間にシフト処理が
生ずる場合がある。このとき、受信側でシフト処理が検
出できず、復号エラーが発生することになる。復号部に
おいて、シフト処理がなければ連続ビットスタッフがあ
ったものとして制御信号を取り除く処理のところを、シ
フト処理があるために、桁上がりで変化したビットを読
み込むという復号エラーを発生してしまう。符号部と復
号部において、符号がどの様な処理（シフト処理、ビッ
ト・スタッフインク処理）によって生成されたのかが一
致していなければ、正常な復号は不可能となる。The decoding side always determines that bit/stuff ink processing is being performed regardless of the processing procedure on the transmitting side. However, on the transmitting side, in the process of consecutive control signals inserted by bit/stuff ink processing, the first and second
A shift operation may occur during the bit-stuff ink operation. At this time, the shift process cannot be detected on the receiving side, resulting in a decoding error. In the decoding section, the shift processing causes a decoding error in that the bits changed due to the carry are read, whereas if the shift processing had not been performed, the control signal would have been removed as if there had been a continuous bit stuff. If the processing (shift processing, bit/stuff ink processing) by which the code is generated does not match between the encoding section and the decoding section, normal decoding will not be possible.

これらの問題に対し、前述した２種類のビット・スタッ
フインク処理に加え、単純に■レジスタ１３長を長＜シ
゛１′′ランの発生確率を小さくするという手法により
、復号エラーが回避する手法がとられてきた。しかし、
算術符号による符号化データを、リアルタイムで伝送あ
るいはメモリ領域への移動を行う際には、この復号エラ
ー状態が増加するのを回避できず、復号エラーに陥ると
いう問題点があった。To solve these problems, in addition to the two types of bit stuffing and ink processing mentioned above, there is a method to avoid decoding errors by simply reducing the probability of occurrence of a long <1'' run by increasing the register 13 length. It has been taken. but,
When data encoded by arithmetic codes is transmitted or moved to a memory area in real time, it is impossible to avoid an increase in the number of decoding error states, resulting in a decoding error.

（発明の目的と特徴） 本発明は、上述した従来技術の問題点を解決するために
なされたもので、算術符号の符号化データのリアルタイ
ム伝送やメモリ領域への移動を、復号エラーなく実現さ
せることが可能な算術符号化における桁上がり伝搬防止
方法を提供することを目的とする。(Objective and Features of the Invention) The present invention has been made to solve the problems of the prior art described above, and enables real-time transmission of encoded data of arithmetic codes and movement to a memory area without decoding errors. The purpose of this invention is to provide a method for preventing carry propagation in arithmetic encoding.

本発明の特徴は、符号化桁上がりレジスタにおいて、桁
上がりが連続して発生した場合、復号エラーを防止する
ための制御信号に加え、挿入制御符号のアドレス情報を
付加して符号化系列を作成すると共にアドレス制御信号
挿入による符号効率劣化を防ぐため、桁上がり緩衝用レ
ジスタを設けた点にある。A feature of the present invention is that when carries occur continuously in the encoded carry register, an encoded sequence is created by adding address information of the insertion control code in addition to a control signal to prevent decoding errors. At the same time, a carry buffer register is provided in order to prevent code efficiency from deteriorating due to address control signal insertion.

（発明の構成と作用） 以下図面を用いて本発明の詳細な説明する。(Structure and operation of the invention) The present invention will be described in detail below using the drawings.

なお、以下の説明では従来構成と同一構成個所について
は同一番号を付し説明の重複を省く。In the following description, the same numbers are given to the same components as in the conventional configuration to avoid redundant explanation.

第３図は本発明による一実施例であり、符号部の構成図
である。第３図で従来構成と異なる点は、Ｗレジスタ１
２と■レジスタ１３との間に、桁上がりの回数を減らす
ための桁上がり緩衝用レジスタ（以下、「Ｐレジスタ」
と称す）を設けると共に、Ｍレジスタ１４と■レジスタ
１３とを監視して複数のビット・スタッフインク処理が
連続して行われた場合にも付加される制御信号の区別を
行うことができるよう°にアドレス制御信号を発生する
アドレス制御信号挿入用レジスタ（以下「Ｑレジスタ」
と称す）１９をビット・スタッフインク処理部２０とし
て設けた点にある。例えば、Ｐビットから成るＰレジス
タを設けた場合、桁上がりは“１”ビットがＰ個連続す
る場合なので、桁上がり回数は確率的に２−’に減少さ
せることができる。FIG. 3 is an embodiment according to the present invention, and is a configuration diagram of a code section. The difference from the conventional configuration in Fig. 3 is that the W register 1
Between 2 and register 13, there is a carry buffer register (hereinafter referred to as "P register") to reduce the number of carries.
In addition to monitoring the M register 14 and the ■register 13, it is possible to distinguish between control signals added even when a plurality of bit/stuff ink processes are performed in succession. Address control signal insertion register (hereinafter referred to as "Q register") that generates an address control signal in
19 is provided as a bit/stuff ink processing section 20. For example, if a P register consisting of P bits is provided, a carry occurs when P consecutive "1" bits occur, so the number of carries can be probabilistically reduced to 2-'.

以下に処理手順について説明する。ビット・スタッフイ
ンク処理部のフローチャートを第４図（ａ）に、又（ａ
）におけるビット・スタッフインク処理の実行部を（ｂ
）に示す。第３図を用いて本発明によるアルゴリズムの
説明をする。The processing procedure will be explained below. The flowchart of the bit/stuff ink processing section is shown in FIG.
) is the execution part of bit/stuff ink processing in (b
). The algorithm according to the present invention will be explained using FIG.

（１）ビット・スタッフインク処理部では、連続する“
１゛がＶビットだけ桁上がり監視レジスタ（■レジスタ
１３）と伝送用バッファ（Ｍレジスタ１４）にまたがっ
て存在するか否かの判定を行う。もし“ｌ”がｖビット
連続する時はビット・スタッフインク処理部２０で同図
（ロ）による処理が行われ、逆にＶビット連続しない時
は終了の工程（後述する（４）項）へ進む。但し、■レ
ジスタ１３にＳビット、Ｍレジスタ１４に（Ｖ−Ｓ）、
併せて合計ｖビットとする。(1) In the bit/stuff ink processing section, consecutive “
It is determined whether or not 1'' exists across the carry monitoring register (register 13) and the transmission buffer (M register 14) by V bits. If "l" is continuous for v bits, the bit/stuff ink processing unit 20 performs the process shown in FIG. move on. However, ■ S bit in register 13, (VS) in M register 14,
Together, the total is v bits.

（２）このステップが、本発明によるアルゴリズムの特
徴となり、同図（ロ）の工程を行う。(2) This step is a feature of the algorithm according to the present invention, and the process shown in FIG.

（Ａ）　　Ｖレジスタ１３よりＭレジスタ１４へ１ビツ
ト伝送する。(A) One bit is transmitted from the V register 13 to the M register 14.

（Ｂ）（＾）項での伝送ビットは、ビット・スタッフイ
ンク処理により発生したもので、かつ、“１”であれば
後述する（３）項の処理を行う。(B) If the transmitted bit in item (^) is generated by the bit stuff ink processing and is "1", then the process in item (3) described later is performed.

（Ｃ）　ｌｏｇ、ｖビットのアドレス制御信号（Ｑレジ
スタ１９）をＭレジスタ１４のＬＳＨに挿入する。ここ
でのアドレス制御信号とは、桁上がりにより“１”に変
化したビットと（Ａ）で挿入した“Ｏ”ビットとのビッ
ト単位での距離のことである。(C) Insert the log, v-bit address control signal (Q register 19) into the LSH of the M register 14. The address control signal here refers to the distance in bits between the bit changed to "1" due to carry and the "O" bit inserted in (A).

（３）■レジスタ１３の（Ｓ−１）番目までを左ヘシフ
トし、■レジスタ１３のＳ番目のビットに“Ｏ″を挿入
する。(3) ■ Shift up to the (S-1)th bit of register 13 to the left, and ■ insert "O" into the S-th bit of register 13.

（４）終了。(4) Finished.

第５図は、本発明による復号部（受信側）のブロック図
である。図中、３１は伝送路又はメモリから入ってくる
バッファメモリであるＳレジスタ、３２は算術演算レジ
スタであるレジスタ、３３は累積和を蓄える為のＡレジ
スタ、３７．３８．３９はオージエントの累積和を作る
ためのＡＣレジスタ、ＳＦレジスタ、ＳＦレジスタであ
る。又、３４はＳレジスタ３１よりＷレジスタ３２へ読
み出すときに、連続“１”ランをＶビットまでカウント
するカウンタ（以下、ｒ検出カウンタ１と称す）、３５
はＳレジスタ３１の空となった位置を知るためのカウン
タ、３６は連続ビット・スタッフインク処理が発生して
いるときＳレジスタ３１よりｌｏｇ２Ｖビットを読み込
むためのアドレス制御信号カンウタであり、本発明の特
徴であるカウンタ３４．３５及び３６で制御信号処理部
４０を構成している。FIG. 5 is a block diagram of a decoding section (receiving side) according to the present invention. In the figure, 31 is an S register that is a buffer memory that enters from a transmission line or memory, 32 is a register that is an arithmetic operation register, 33 is an A register for storing cumulative sums, and 37, 38, and 39 are arient cumulative sums. These are AC register, SF register, and SF register for creating. Further, 34 is a counter (hereinafter referred to as r detection counter 1) that counts continuous "1" runs up to V bits when reading from the S register 31 to the W register 32;
36 is an address control signal counter for reading log2V bits from the S register 31 when continuous bit stuff ink processing is occurring. The characteristic counters 34, 35 and 36 constitute a control signal processing section 40.

第６図は本発明によると、復号部における制御信号処理
部４０の処理手順を示す。FIG. 6 shows the processing procedure of the control signal processing section 40 in the decoding section according to the present invention.

（Ｉ）検出カウンタ３４はＳレジスタ３１から読み込ん
だビットが、符号部の■レジスタ１３長分であるＶビッ
ト連続して“１”ランが続いているか否を判定し、連続
していれば次の工程（ｎ）に進み、逆に連続していない
時はアドレス制御信号カウンタ３６が“０”の状態であ
るかの判定を行う。(I) The detection counter 34 determines whether or not the bits read from the S register 31 continue to run as "1" by V bits, which is the length of register 13 in the sign section. Proceeding to step (n), on the other hand, if they are not consecutive, it is determined whether the address control signal counter 36 is in the "0" state.

カウンタ３６の状態が“０”でないならば次の工程（Ｉ
Ｉ）へ進み、′０”ならば処理部４０の工程を終了する
。If the state of the counter 36 is not “0”, the next step (I
Proceed to I), and if it is '0', the process of the processing section 40 is completed.

（ｎ）ビット・スタッフインク処理が行われたとして、
Ｓレジスタ３１よりもう１ビット読み込まれ、Ｗレジス
タ３２に伝送される。(n) Assuming that bit/stuff ink processing is performed,
One more bit is read from the S register 31 and transmitted to the W register 32.

（ＩＩ）アドレス制御信号カウンタ３６をデクリメント
する。(II) Decrement the address control signal counter 36.

（ＩＶ） （Ａ）上述の（ＩＩ）項で読み込まれたビットが“０゛
ならば、後述する（Ｖ）項の処理を行い、°“１°゛な
らば、連続したビット・スタッフインク検出カウンタ３
４をインクリメントする。(IV) (A) If the bit read in item (II) above is “0”, perform the processing in item (V) described below; if “1°”, consecutive bits/stuff ink are detected. counter 3
Increment 4.

（Ｂ）検出カウンタ３４がＶビットと等しいかまたは小
さいとき後述（Ｖ）項の処理を行い、逆に大きい時は次
の（Ｃ）項の処理を行う。(B) When the detection counter 34 is equal to or smaller than the V bit, the process in section (V) described below is performed, and when it is larger, on the contrary, the process in the next section (C) is performed.

（Ｃ）　　Ｓレジスタ３１よりｌｏｇ２ｖビットだけ、
アドレス制御カウンタ３６へ読み込まれる。(C) Only log2v bits from S register 31,
The address is read into the address control counter 36.

（Ｖ）アドレス制御カウンタ３６が“０゛となったとき
前述の（ｎ）項の処理に戻り、そうでなければ処理部４
０の処理を終了する。(V) When the address control counter 36 reaches "0", the process returns to the above-mentioned item (n); otherwise, the processing section 4
0 processing ends.

（Ｖｌ）終了。(Vl) Finished.

表　　　　　　３ 表３に、本発明により作成された算術符号化の例を示す
。アドレス制御情報とは、桁上がりにより２度目にビッ
ト・スタッフインク処理が発生する時、桁上がりによっ
て１゛′に変化したビットと、ビット・スタッフインク
により挿入したビット“０″゛に対して挿入するもので
ある。このとき、表３の例では２つのビットの距離が３
であるため、１ｏｇ２２２＝　２ビツトで距離３を表し
、Ｗレジスタ３２に書き込む際に、連続“１”ランのあ
とに“１１”を挿入する。Table 3 Table 3 shows an example of an arithmetic encoding created according to the present invention. Address control information is inserted when bit/stuff ink processing occurs for the second time due to a carry, for the bit changed to 1' by the carry and the bit "0" inserted by bit stuff ink. It is something to do. At this time, in the example of Table 3, the distance between the two bits is 3
Therefore, 1og222=2 bits represents a distance of 3, and when writing to the W register 32, "11" is inserted after a continuous "1" run.

上述のように、本発明の符号化部ではＷレジスタ１２と
■レジスタ１３との間に桁上がりの回数を低減させるた
めの桁上がり緩衝用レジスタ（Ｐレジスタ）　１８を設
けると共に、桁上がりとシフトとが同時に発生した場合
の如く制御信号が複数連続した時に制御信号を判別する
ためのアドレス制御信号を付加することより、桁上がり
時に生じる復号エラーを防止するようにしたものである
。As mentioned above, in the encoding section of the present invention, a carry buffer register (P register) 18 is provided between the W register 12 and the ■ register 13 to reduce the number of carries, and the carry buffer register (P register) 18 is provided between the W register 12 and the By adding an address control signal for determining a control signal when a plurality of control signals occur in succession, such as when a plurality of control signals occur at the same time, decoding errors that occur at the time of a carry are prevented.

第７図は本発明の算術符号化と従来の算術符号化との符
号化効率の比較図である。図中、■の特性は従来の算術
符号化で■レジスタ１３だけでビット・スタッフインク
処理を行った場合、■の特性は従来の算術符号化でＭレ
ジスタ１４と■レジスタ１３とによりビット・スタッフ
インク処理を行った場合、■の特性は本発明による算術
符号化で制御信号にアドレス制御信号（２ビツト）を付
加した場合、■の特性は本発明による算術符号化でＰレ
ジスタ１８とアドレス制御信号とを用いた場合をそれぞ
れ示している。FIG. 7 is a comparison diagram of coding efficiency between arithmetic coding according to the present invention and conventional arithmetic coding. In the figure, the characteristics of ■ are conventional arithmetic coding when bit stuffing and ink processing is performed using ■ register 13 only, and the characteristics of ■ are conventional arithmetic encoding and bit stuffing is performed using register 14 and ■ register 13. When ink processing is performed, the characteristic of ■ is the arithmetic encoding according to the present invention, and when an address control signal (2 bits) is added to the control signal, the characteristic of ■ is the arithmetic encoding according to the present invention, when the address control signal (2 bits) is added to the P register 18. The cases in which signals and signals are used are shown respectively.

同図から明らかなように、本発明の特徴のひとつである
アドレス制御信号（２ピント）を単に付加した場合（■
の特性）には伝送すべき情報が増えるために符号化効率
が低下するが、さらに桁上がりの回数を低減させるＰレ
ジスタ１８と組み合われること（■の特性）により、結
果的に従来の算術符号化よりも符号化効率が向上する。As is clear from the figure, when the address control signal (2 pins), which is one of the features of the present invention, is simply added (■
Although the encoding efficiency decreases due to the increase in the amount of information to be transmitted, the combination with the P register 18 that further reduces the number of carries (characteristic of Encoding efficiency is improved compared to digitization.

第８図は本発明による算術符号化と従来の算術符号化に
よる量子化ステップサイズと復号エラー発生確率との比
較図であり、本発明の算術符号化では復号エラー発生確
率をほぼ零にすることができる。FIG. 8 is a comparison diagram of the quantization step size and decoding error occurrence probability between arithmetic coding according to the present invention and conventional arithmetic coding. Can be done.

このように、本発明は連続符号である算術符号化の桁上
がりによって生じる復号エラー防止をすると共に符号化
効率を改善することができる。In this manner, the present invention can prevent decoding errors caused by carry in arithmetic coding, which is a continuous code, and improve coding efficiency.

（発明の効果） 以上、詳細に説明したように本発明によれば、算術符号
をＦＩＦＯ型で行う際、桁上がり防止のために、数ビッ
ト長から成るＰレジスタ１８を設けると共に制御信号と
そのアドレス情報を符号化系列に挿入することによって
復号エラーを防止するため、復号化不能状態を完全に回
避することができ、かつ符号化効率も向上させることが
できる。従って、量子化サイズステップに関係な（高符
号化率を有する算術符号化の利点を用いて画像情報や音
声情報等のデータ圧縮技術に適用することが出来、その
効果は大である。(Effects of the Invention) As described above in detail, according to the present invention, when performing arithmetic coding in FIFO type, the P register 18 having a length of several bits is provided in order to prevent carry, and the control signal and the Since decoding errors are prevented by inserting address information into the encoded sequence, it is possible to completely avoid a state in which decoding is not possible, and it is also possible to improve encoding efficiency. Therefore, the advantages of arithmetic coding related to quantization size steps (having a high coding rate) can be applied to data compression techniques for image information, audio information, etc., and the effect is great.

第１図は従来の算術符号化とハフマン符号化との符号化
効率−量子化ステップサイズ特性、第２図は従来の算術
符号化部のブロック図、第３図は本発明による算術符号
化部のブロック図、第４図は本発明によるビットスタッ
フィング処理の流れ図、第５図は本発明による算術符号
を用いた復号部のブロック図、第６図は本発明による制
御信号処理部の流れ図、第７図は本発明による算術符号
化と従来の算術符号化との符号化率の比較図、第８図は
本発明による算術符号化と従来の算術符号化との復号エ
ラー発生確率の比較図である。 １１、３３・・・Ａレジスタ、１２．３２・・・Ｗレジ
スタ、１３・・・■レジスタ、１４・・・Ｍレジスタ、
１５．３７・・・へＧレジスタ、１６．３８・・・ＳＦ
レジスタ、１７．３９・・・３Ｍレジスタ、１８・・・
Ｐレジスタ、１９・・・Ｑレジスタ、２０・・・ビット
・スタッフインク処理部、３１・・・Ｓレジスタ、３４
・・・連続１ビツト検出カウンタ、３５・・・バッファ
制御用カウンタ、３６・・・アドレス制御信号カウンタ
。 特許出願人　　国際電信電話株式会社 ′代理人　弁理士火爆　学 第１図 茅２図 第６図 第７図 ミ≠　　　１ 十 ステ７７＋゛す′イス 第８図 ステ、７８サイス゛Fig. 1 shows the coding efficiency-quantization step size characteristics of conventional arithmetic coding and Huffman coding, Fig. 2 is a block diagram of the conventional arithmetic coding unit, and Fig. 3 shows the arithmetic coding unit according to the present invention. 4 is a flowchart of the bit stuffing process according to the present invention, FIG. 5 is a block diagram of the decoding section using arithmetic codes according to the present invention, and FIG. 6 is a flowchart of the control signal processing section according to the present invention. Figure 7 is a comparison diagram of the coding rate between arithmetic encoding according to the present invention and conventional arithmetic encoding, and Figure 8 is a diagram comparing the probability of decoding error occurrence between arithmetic encoding according to the present invention and conventional arithmetic encoding. be. 11, 33...A register, 12.32...W register, 13...■ register, 14...M register,
15.37...G register, 16.38...SF
Register, 17.39...3M register, 18...
P register, 19...Q register, 20...Bit stuff ink processing section, 31...S register, 34
. . . Continuous 1-bit detection counter, 35 . . . Buffer control counter, 36 . . . Address control signal counter. Patent Applicant: International Telegraph and Telephone Co., Ltd. Agent: Patent Attorney Hibaku

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