JPH06338803A

JPH06338803A - 符号伝送装置

Info

Publication number: JPH06338803A
Application number: JP15118893A
Authority: JP
Inventors: Noriaki Tsuchiya; 徳明土屋
Original assignee: Fuji Xerox Co Ltd
Current assignee: Fujifilm Business Innovation Corp
Priority date: 1993-05-28
Filing date: 1993-05-28
Publication date: 1994-12-06
Anticipated expiration: 2016-04-03
Also published as: JP3152017B2

Abstract

(57)【要約】【目的】複数のシンボル系列に対し、スタッフビット
のない符号データを生成し、かつ、符号化処理を停止さ
せることなく、伝送路へ送出することのできる符号伝送
装置を提供する。【構成】Ｃレジスタ１から、キャリービットとｎビッ
ト分のデータが第１のレジスタ２に転送される。ｎビッ
トがオール１である場合は、カウンタ４を＋１する。違
うときは、ｎビットが第２のレジスタ３に格納され、次
のデータのキャリービットが１のとき、加算器９で１加
算する。第２のレジスタ３のデータは、セレクタ５を通
じてメモリバッファ７へ転送される。また、カウンタ４
の値が０でない場合は、カウント値をメモリバッファ７
へ転送する。メモリバッファ７への転送の際には、ＦＬ
ＡＧ生成回路６で生成されるフラグが付加される。デコ
ーダ８は、フラグを参照し、純粋な符号データに変換し
て伝送路１０へ送出する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、算術符号を発生して伝
送を行なう符号伝送装置に関するものである。

【０００２】

【従来の技術】エントロピー符号化の１つの方式に算術
符号化がある。算術符号は、シンボルの生起確率に応じ
てある区間を順次分割し、最終的にシンボル列に対し、
ある部分区間を割当て、これを符号とする方式である。
この区間分割で示される符号は、符号系列のシフトと区
間信号との加算で生成される。

【０００３】符号生成時の問題点として、符号が加算に
よって生成されるため、桁上がり伝播がある。この桁上
がり伝播を処理する方法としては、「マルチメディア符
号化の国際標準」、丸善、ｐ．７４−７６にも示されて
いるように、桁上がり待機方式と桁上がり情報送信方
式、すなわち、ビットスタッフィング方式がある。桁上
がり待機方式では、符号ビットが確定するまで、伝送せ
ずにシンボルを記憶しておき、確定した時点で初めて伝
送する。そのため、最終シンボルの処理が終わるまで符
号が確定しない場合が考えられる。

【０００４】このような場合にも対応するため、ビット
スタッフィング方式がある。この方式は、例えば、特開
平３−２３５４２７号公報，特開平３−４４１１６号公
報等にも記載されている。この方式によると、ある一定
数の連続する「１」の後に桁上がりを吸収できる制御用
ビットを挿入するため、各シンボルを待機せずに伝送す
ることができ、符号発生の際の遅延問題は解決できる。
しかし、符号長が長くなる、復号側で制御用ビットを除
去する処理が必要となるという問題がある。

【０００５】また、この方式を用いて符号を生成した
後、制御用ビットの除去を符号側で行なおうとすると、
待機方式と同様に、符号の最終の制御用ビットを判定し
ないと最終的に純粋な符号が生成できないため、処理に
時間がかかり、複数のシンボル系列を順に符号化する際
に、この制御用ビットの除去処理のため、符号化の処理
が途中で停止するという問題点があった。

【０００６】

【発明が解決しようとする課題】本発明は、上述した事
情に鑑みてなされたもので、複数のシンボル系列に対
し、スタッフビットのない符号データを生成し、かつ、
符号化処理を停止させることなく、伝送路へ送出するこ
とのできる符号伝送装置を提供することを目的とするも
のである。

【０００７】

【課題を解決するための手段】本発明は、算術符号を生
成する符号伝送装置において、算術符号化に必要な加算
およびシフトを行なって得られる符号系列を保持する算
術演算レジスタと、該算術演算レジスタに保持されてい
る符号系列の上位より桁上がりが伝播するビットをｎビ
ット単位でカウントするカウンタと、確定した符号およ
び前記カウンタのカウント値をその属性を示す記号と共
に保持する保持手段と、該保持手段に保持されている内
容を読み出し前記属性を示す記号に基づき符号データへ
デコードするデコード手段を備えたことを特徴とするも
のである。

【０００８】

【作用】本発明によれば、加算およびシフト処理がなさ
れた符号系列を順に参照し、符号系列の上位より桁上が
りが伝播する場合には、伝播するビットをｎビット単位
でカウントし、カウント値に、その属性を示す記号を付
して保持手段に保持させる。保持手段に保持されている
属性を示す記号が付された内容は、各符号系列ごとに処
理可能なデータであるので、待機することなく、順次、
デコード手段により符号データとして送出することがで
きる。このとき、桁上がりを伝播するための制御用ビッ
トの処理によって、符号化処理が一時停止することはな
い。また、符号データに制御用ビットは付加されないの
で、符号長が長くなることはない。

【０００９】

【実施例】図１は、本発明の符号伝送装置の一実施例を
示す概略構成図、図２は、ビット構成の説明図である。
図中、１はＣレジスタ、２は第１のレジスタ、３は第２
のレジスタ、４はカウンタ、５はセレクタ、６はＦＬＡ
Ｇ生成回路、７はメモリバッファ、８はデコーダ、９は
加算器、１０は伝送路である。

【００１０】Ｃレジスタ１には、図２（Ａ）に示すよう
に、算術符号化に必要な１シンボルごとの加算、シフト
を終了した符号データが格納される。第１のレジスタ２
には、算術演算のｎ回シフトが行なわれるごとに、図２
（Ｂ）に示すように、Ｃレジスタ１の上位ｎ＋１ビット
分のデータが転送され、格納される。このとき、Ｃレジ
スタ１のｎ＋１の位置のビット（以下、キャリービット
と呼ぶ）は、ｎ回シフトした時点で桁上がりが発生した
ことを意味する。キャリービットが０、つまり、桁上が
りが発生しなかった場合、図２（Ｃ）に示すように、第
１のレジスタ２の下位ｎビットが第２のレジスタ３へ転
送され、保持される。ただし、ｎビットがオール１であ
る場合は転送されず、カウンタ４がインクリメントされ
る。

【００１１】次のデータが第１のレジスタ２へ転送され
た時、キャリービットが１、つまり桁上がりが発生した
場合、先に第２のレジスタ３に転送したデータに対し
て、加算器９で１だけ加算する。加算されたデータは、
桁上がりの可能性のない確定した符号データであるの
で、セレクタ５を通じてメモリバッファ７へ転送され
る。また、キャリービットが０である場合も、ｎビット
がオール１である場合を除き、第２のレジスタ３のデー
タは確定した符号データであるので、メモリバッファ７
へ転送される。

【００１２】また、カウンタ４の値が０でない場合、キ
ャリービットが１であれば（カウント値×ｎ）ビットが
実際には０の符号となり、キャリービットが０であれば
（カウント値×ｎ）ビットが１の符号となる。しかし、
本発明の構成では、カウント値を分解せず、直接、カウ
ント値をメモリバッファ７へ書き込む。

【００１３】第２のレジスタ３の値、もしくは、カウン
タ４のカウント値をメモリバッファ７へ書き込む際、こ
れらの区別をするため、ＦＬＡＧ生成回路６で生成され
るフラグが付加される。

【００１４】デコーダ８では、メモリバッファ７のデー
タを読み出し、フラグを参照して、カウント値の場合に
はこれを分解し、純粋な符号データとして伝送路１０へ
送出する。

【００１５】図３は、本発明の符号伝送装置の一実施例
における具体例を示す概略構成図である。図中、図１と
同様の部分には、同じ符号を付して説明を省略する。１
１はＡＮＤ回路、１２はＯＲ回路、１３は減算器、１４
はメモリ切替信号、１５はセレクタ、１６はメモリＡ、
１７はメモリＢである。この具体例では、図１のビット
数ｎを８とした。またメモリバッファ７をピンポンバッ
ファとし、ある一定幅で各々のリードライトを切り換え
て使用できるように構成した。

【００１６】ＡＮＤ回路１１は、第１のレジスタ２に保
持されたキャリービットを含む９ビットの符号データの
うち、キャリービット以外の８ビットすべてが「１」で
あることを検出する。検出結果はカウンタ４に伝えら
れ、カウンタ４がインクリメントされる。

【００１７】カウンタ４は、符号数が８個ごとにカウン
トアップされ、一定幅の符号数をカウントできるよう
に、８＋ｍビットのビット長を有している。しかし、第
２のレジスタ３のビット幅に合わせて、８ビット幅でカ
ウント値の出力を行なう。そのために、ビット幅に対応
する減算器１３を設けており、カウンタ４は、カウント
値が２５６ごとにメモリＡ１６またはメモリＢ１７に対
してデータを出力し、減算器１３により、２５６だけカ
ウント値が減算される。これにより、カウント値をビッ
ト幅ごとに数回に分けて書き込みを行なっている。

【００１８】ＯＲ回路１２は、カウンタ４のカウント値
が０か否かを判定するものであり、判定結果がＦＬＡＧ
生成回路６に入力される。ＦＬＡＧ生成回路６は、メモ
リへの書き込みデータのフラグを２ビットで出力する。
図４は、フラグの内容の説明図である。ＦＬＡＧ生成回
路６から出力されるフラグが「００」の場合は、通常の
符号データを示し、第２のレジスタ３からメモリに転送
されるデータに付加される。また、フラグが「０１」の
場合も、通常の符号データを示すが、次のデータからカ
ウント値となることを示している。フラグが「１０」，
「１１」の場合は、メモリへの書き込みデータがカウン
ト値であることを示しており、フラグが「１０」の場合
は、カウント値×８ビットが全て０の符号データとなる
ことを、また、フラグが「１１」の場合は、１の符号デ
ータとなることを示している。符号化すべきデータが終
了した場合には、「００」の次に「１１」のフラグを出
力する。

【００１９】図３に戻り、メモリＡ１６およびメモリＢ
１７は、メモリ切替信号１４により書き込みおよび読み
出しが切り替えられ、ピンポンバッファとして機能す
る。また、これらのメモリの出力は、同じくメモリ切替
信号１４により制御されるセレクタ１５により、読み出
し側のメモリが選択される。メモリＡ１６およびメモリ
Ｂ１７には、セレクタ５を介して送られて来る８ビット
の符号データまたはカウント値のほか、それと対応する
ＦＬＡＧ生成回路から送られて来る２ビットのフラグを
保持する。メモリから読み出されるデータは、フラグ付
きの１０ビットのデータである。デコーダ８では、フラ
グを解釈し、カウント値の展開等の処理を行なって、符
号データを伝送路１０に出力する。

【００２０】図５は、本発明の符号伝送装置の一実施例
における具体例の動作の流れを示すフローチャートであ
る。このフローチャートは、１つのデータごとの処理の
流れを示している。Ｓ２１において、Ｃレジスタ１にお
いて、算術演算の８回シフトが行なわれた後、上位９ビ
ットが第１のレジスタ２に転送される。Ｓ２２では、第
１のレジスタ２の最上位ビット、すなわち、キャリービ
ットが判定される。キャリービットが０であった場合
は、桁上がりは発生しなかったことを意味するので、Ｓ
２３に進み、桁上がりがない場合の処理を行なう。

【００２１】Ｓ２３では、第１のレジスタ２の他の８ビ
ットがｆｆ（１６進）、すなわち、オール「１」である
かどうかが判断される。ｆｆ（１６進）であった場合に
は、次にＣレジスタ１から桁上がりが伝播してくる可能
性があるため、Ｓ２４において、カウンタ４をインクリ
メントし、このデータに対する動作を終了する。

【００２２】Ｓ２３において、ｆｆ（１６進）でない場
合は、先に第２のレジスタ３に転送された符号データが
確定したことを示すので、メモリへの転送動作へ移行す
る。Ｓ２５において、カウント値（ＣＮＴ）を判断し、
０であった場合は、Ｓ２６で第２のレジスタ３に保持さ
れている符号データが、セレクタ５を通り、メモリＡ１
６またはメモリＢ１７に書き込まれる。このとき、ＦＬ
ＡＧ生成回路６で、メモリに書き込まれるデータが通常
の符号であることを示すフラグ「００」が生成され、第
２のレジスタ３の符号データに付加され、メモリに書き
込まれる。

【００２３】Ｓ２５において、ＣＮＴ≠０であった場合
は、Ｓ２７へ進む。この時点で、それまでカウンタ４に
よりカウントしていたデータが確定するので、カウント
値の出力を行なう。Ｓ２７において、フラグ「０１」が
生成され、先と同様に、第２のレジスタ３の符号データ
に付加され、メモリへ書き込まれる。次に、Ｓ２８にお
いて、カウンタ４の値が２５６未満であるかどうかが判
断される。これは、第２のレジスタ３のビット幅を８と
したため、メモリへの書き込みの際のビット幅を合わせ
るための処理である。２５６未満であった場合には、Ｓ
２９において、カウント値（ＣＮＴ）がセレクタ５を通
り、フラグ「１１」と共にメモリＡ１６またはメモリＢ
１７へ直接書き込まれる。また、２５６以上であった場
合には、Ｓ３０において、フラグ「１１」と共に、００
（１６進）がメモリＡ１６またはメモリＢ１７に書き込
まれる。フラグ「１１」は、カウント値×８ビットが全
て１の符号データということを意味している。さらに、
カウンタ４の値を減算器１３で２５６だけ減算して、Ｓ
２８へ戻る。そして、カウント値が２５６未満、つま
り、カウント値をメモリへ全て転送できるまでＳ２８か
らＳ３０のループが繰り返される。

【００２４】全て終了した後、Ｓ３８においてカウンタ
４はクリアされ、第１のレジスタ２の符号データは第２
のレジスタ３へ転送され、次のＣレジスタ１からのデー
タ転送を得る。

【００２５】さて、Ｓ２２においてキャリービットが１
である場合は、桁上がりが発生したことを示す。そのた
め、まず、Ｓ３１において、第２のレジスタ３の値を加
算器９でインクリメントする。次に、Ｓ２５からＳ３０
と同様に、Ｓ３２からＳ３７において、カウント値を判
断してフラグと共に、順次、メモリＡ１６またはメモリ
Ｂ１７に書き込まれる。このとき、カウンタ値を書き込
む際に一緒に書き込まれるフラグは「１０」となる。こ
のフラグの値は、桁上がりが発生したため、カウント値
×８ビットが全て０の符号データであることを意味す
る。

【００２６】以上の動作を繰り返すことにより、符号デ
ータは、メモリＡ１６およびメモリＢ１７に書き込まれ
る。データ終了時にはフラグ「００」の後、次のアドレ
スにフラグ「１１」を書き込み、通常符号と区別する。

【００２７】次に、メモリ切り換え、および、デコーダ
８について説明する。図６，図７は、メモリ切り換えの
一例を示すタイミングチャートである。図６は、ある原
稿を符号化する際に、原稿データをいくつかに分割し、
使用するメモリを切り換える場合の例を示している。ペ
ージ同期信号＝Ｈで有効データが入力されるものとす
る。また、切り換え信号＝ＬでメモリＡ１６への書き込
みおよびメモリＢ１７からの読み出しとなり、切り換え
信号＝ＨでメモリＡ１６からの読み出しおよびメモリＢ
１７への書き込みの動作が行なわれるものとする。

【００２８】まず、ページ同期信号＝Ｈかつ切り換え信
号＝Ｌであるとき、図３において、符号データおよびカ
ウント値は、セレクタ５を介してメモリＡ１６に書き込
まれると同時に、先に書き込まれているメモリＢ１７の
データがセレクタ１５を介して、デコーダ８へ読み出さ
れる。また、ページ同期信号＝Ｈかつ切り換え信号＝Ｈ
であるときは、符号データおよびカウント値は、メモリ
Ｂ１７に書き込まれると同時に、先に書き込まれている
メモリＡ１６のデータがセレクタ１５を介してデコーダ
８へ読み出される。これらの動作を、ある一定幅、すな
わち、切り換え信号幅で交互に行なう。デコーダ８では
フラグの値に従い、カウント値を分解し、純粋な符号デ
ータとして伝送路１０へ送出する。データ終了を意味す
るフラグを検出した時点で動作を停止する。

【００２９】メモリからのデータの読み出しの際には、
あるデータを読み出して純粋な符号として伝送路に出力
する間に、次のアドレスを読み出すように構成すれば、
途中停止することなく、符号データを送出することがで
きる。

【００３０】図７においては、数枚の原稿を連続して符
号化する際のメモリ切り換えの１例を示している。この
例では、ある１枚の原稿を符号化する際に、メモリの片
方を連続して使用し、原稿１枚単位でメモリを切り換え
て使用する。

【００３１】このように、メモリの切り換えはある単位
ごとに行なえばよく、デコーダ８以降の処理速度と、メ
モリへの書き込み速度との関係で設定することにより、
効率的な処理を符号化を行なうことができる。

【００３２】具体的なデータとして、Ｃレジスタ１か
ら、桁上がりが伝播する可能性のあるデータが連続して
２０４８個送出された場合を考える。従来のビットスタ
ッフィング法では、２０４８個の中に桁上がり防止用の
ビット０と区切り符号を挿入する。この桁上がり防止用
ビットを除去するために、例えば、特開平３−２３５４
２７号公報では、シフトレジスタにて、ある一定数シフ
トした後次ビットを除去し、桁上がりを上位に伝播する
という操作を行なう。この従来の方式では、２０４８個
の最終データまで読み込み、順に桁上がりを除去しなけ
ればならないので、非常に時間がかかる。これに対し、
本発明によれば、カウント値が１００（１６進）につき
１回のメモリアクセスを行なうので、カウント値＝２０
４８＝８００（１６進）であるから、メモリに書き込む
際は８回のアクセスで済む。また、メモリから読み出す
際には、すでに符号は確定しているため、１アドレスの
データを読み出し、フラグに従い、２５６個の符号を送
出するという動作を、１アドレスずつ行なえばよいた
め、高速に処理することができる。

【００３３】また、図３に示した構成では、ピンポンバ
ッファの構成を用いているので、ある一定数の符号を各
々のメモリに交互に書き込むようにすると、途中、桁上
がり伝播の恐れのあるデータが発生しても、Ｃレジスタ
１→メモリ、メモリ→デコーダ→伝送路のいずれのパス
も１回も停止することなく処理を行なえ、かつ伝送路か
らはスタッフビットのない純粋な符号データが出力され
るため、従来よりもスループットを格段に向上させるこ
とができる。

【００３４】上述の具体例の説明では、データ転送ビッ
ト数ｎを８としたが、本発明はこれに限らず、他の値で
構成することも可能である。

【００３５】

【発明の効果】以上の説明から明らかなように、本発明
によれば、算術符号化において、加算およびシフト処理
がなされた符号系列から、桁上がりを伝播するための制
御用ビットを含まない、データ長の短い符号データを生
成し、従来のように待機することなく、また、符号化処
理を停止させることなく、高速に符号化処理を行ない、
符号データを伝送路へ送出することができるという効果
がある。

【図面の簡単な説明】

【図１】本発明の符号伝送装置の一実施例を示す概略
構成図である。

【図２】ビット構成の説明図である。

【図３】本発明の符号伝送装置の一実施例における具
体例を示す概略構成図である。

【図４】フラグの内容の説明図である。

【図５】本発明の符号伝送装置の一実施例における具
体例の動作の流れを示すフローチャートである。

【図６】原稿データをいくつかに分割し、使用するメ
モリを切り換える場合のメモリ切り換えの一例を示すタ
イミングチャートである。

【図７】数枚の原稿を連続して符号化する際のメモリ
切り換えの一例を示すタイミングチャートである。

【符号の説明】

１Ｃレジスタ、２第１のレジスタ、３第２のレジ
スタ、４カウンタ、５セレクタ、６ＦＬＡＧ生成
回路、７メモリバッファ、８デコーダ、９加算器、
１０伝送路、１１ＡＮＤ回路、１２ＯＲ回路、１
３減算器、１４メモリ切替信号、１５セレクタ、
１６メモリＡ、１７メモリＢ。

Claims

【特許請求の範囲】

【請求項１】算術符号を生成する符号伝送装置におい
て、算術符号化に必要な加算およびシフトを行なって得
られる符号系列を保持する算術演算レジスタと、該算術
演算レジスタに保持されている符号系列の上位より桁上
がりが伝播するビットをｎビット単位でカウントするカ
ウンタと、確定した符号および前記カウンタのカウント
値をその属性を示す記号と共に保持する保持手段と、該
保持手段に保持されている内容を読み出し前記属性を示
す記号に基づき符号データへデコードするデコード手段
を備えたことを特徴とする符号伝送装置。