(57)【要約】【課題】２値算術符号化装置において高速に再正規化することを可能にする。【解決手段】２値信号系列の存在区間の幅（以下、ｒａｎｇｅという。）と下端（以下、ｌｏｗという。）を一括して拡大する。ｌｏｗを２倍に拡大する処理を最大８回行う可能性があるとき、１回目から８回目までの各拡大処理に対応する８個のｉビットｌｏｗ拡大回路を設ける。個々のｉビットｌｏｗ拡大回路からは、０、１、または未確定のいずれかのビット出力、及びｉ回目のｌｏｗの拡大処理に対応するｌｏｗが出力される。零検出回路２は、ｒａｎｇｅについてＭＳＢから下位ビット側に向けて連続する０を検出する。ビット出力集約回路１１は、零検出回路２によって０と検出されたビットに対応するｉビットｌｏｗ拡大回路からのビット出力を集める。ｌｏｗ選択回路１２は、０と検出されたビットの中で最下位のビットに対応するｉビットｌｏｗ拡大回路から出力されるｌｏｗを選択する。【選択図】図５
2007300444.tif 000002
【特許請求の範囲】
【請求項１】
符号化の状態が２値信号系列の存在区間の幅と下端で表され、再正規化により該存在区間の幅と下端が１ビットからｎビットまで左論理シフトされて拡大される可能性がある２値算術符号化装置であって、
拡大される可能性がある１ビットからｎビットまでの個々のシフト数に対応して設けられ、０、１、または未確定の３種類のいずれかのビット出力と、拡大された存在区間の下端の値が出力されるｎ個の存在区間下端拡大部と、
再正規化による該存在区間の下端のシフト数がａビット（１≦ａ≦ｎの整数）であるとき、１ビットからａビットまでのシフト数に対応する前記存在区間下端拡大部からのビット出力を集めるビット出力集約部と、
該ａビットのシフト数に対応する前記存在区間下端拡大部から出力される存在区間の下端を選択する存在区間下端選択部と、
を有することを特徴とする２値算術符号化装置。
【請求項２】
前記ビット出力集約部から出力される個々のビット出力が未確定のときビット１を設定し、０または１のときビット０を設定することによってビット系列Ｓを作成し、かつ、前記ビット出力集約部から出力される個々のビット出力が１のときビット１を設定し、０または未確定のときビット０を設定することによってビット系列Ｃを作成し、該ビット系列Ｓを１ビット右論理シフトして該ビット系列Ｃと加算することによって、未確定が含まれるビット出力系列を確定したビット出力系列に変換するビット出力変換部、
を有することを特徴とする請求項１記載の２値算術符号化装置。
【請求項３】
動画像符号化規格Ｈ．２６４におけるＣＡＢＡＣに準拠した２値算術符号化装置であって、
拡大される可能性がある１ビットから７ビットまでの個々のシフト数に対応して設けられ、０、１、または未確定の３種類のいずれかのビット出力と、拡大された存在区間の下端の値が出力される７個の存在区間下端拡大部と、
再正規化による該存在区間の下端のシフト数がａビット（１≦ａ≦７の整数）であるとき、１ビットからａビットまでのシフト数に対応する前記存在区間下端拡大部からのビット出力を集めるビット出力集約部と、
該ａビットのシフト数に対応する前記存在区間下端拡大部から出力される存在区間の下端を選択する存在区間下端選択部と、
前記ビット出力集約部から出力される個々のビット出力が未確定のときビット１を設定し、０または１のときビット０を設定することによってビット系列Ｓを作成し、かつ、前記ビット出力集約部から出力される個々のビット出力が１のときビット１を設定し、０または未確定のときビット０を設定することによってビット系列Ｃを作成し、該ビット系列Ｓを１ビット右論理シフトして該ビット系列Ｃと加算することによって、未確定が含まれるビット出力系列を確定したビット出力系列に変換するビット出力変換部と、
を有することを特徴とする２値算術符号化装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、算術符号化装置に関するものであり、特に、動画像符号化規格Ｈ．２６４におけるＣＡＢＡＣ
（ Ｃｏｎｔｅｘｔ−ｂａｓｅｄ  Ａｄａｐｔｉｖｅ  Ｂｉｎａｒｙ  Ａｒｉｔｈｍｅｔｉｃ  Ｃｏｄｉｎｇ；コンテキスト適応型２値算術符号化方式） に準拠した算術符号化装置に適したものである。
【背景技術】
【０００２】
ＣＡＢＡＣでは多値のシンタックスエレメントを２値信号（０と１の信号）に変換し、この２値信号（以下、ｓｙｍｂｏｌという。）を算術符号化する。図１は、ＣＡＢＡＣに準拠した算術符号化を行うBiari_encode_symbol処理フローである（例えば、非特許文献１参照）。ＣＡＢＡＣでは、符号化の状態をｓｙｍｂｏｌ系列の存在区間の幅（以下、ｒａｎｇｅという。）と下端（以下、ｌｏｗという）で表す。ｒａｎｇｅとｌｏｗのビット幅はそれぞれ９ビットと１０ビットであり、スライスの先頭でｒａｎｇｅは０ｘ１ＦＥ（０ｘは、１６進数であることを示す。以下、同じ。）、ｌｏｗは０ｘ０００に初期化される。０と１のうち、発生確率の低い方がＬＰＳ（Ｌｅａｓｔ  Ｐｒｏｂａｂｌｅ  Ｓｙｍｂｏｌ）に割り当てられ、発生確率の高い方がＭＰＳ（Ｍｏｓｔ  Ｐｒｏｂａｂｌｅ  Ｓｙｍｂｏｌ）に割り当てられる。ＬＰＳの発生確率（ｒＬＰＳ）は、発生確率の状態を示す番号（以下、ｓｔａｔｅという。）とｒａｎｇｅによってテーブル（rLPS_table_64x4）を引くことにより求められる（ステップＳ１）。一方、ＭＰＳの発生確率は、ｒａｎｇｅからＬＰＳの発生確率（ｒＬＰＳ）を減算することで算出される（ステップＳ２）。
【０００３】
ｓｙｍｂｏｌがＬＰＳであるときのｒａｎｇｅとｌｏｗの変化を図２（ａ）に示す。ｓｙｍｂｏｌがＬＰＳであるとき、ＭＰＳの発生確率を加算することによってｌｏｗが更新され、ｒａｎｇｅにはＬＰＳの発生確率（ｒＬＰＳ）が設定される（ステップＳ４）。ｓｔａｔｅ＝０であれば、次の符号化状態における０と１の発生確率の大小が逆転すると予想されるため、ＭＰＳに対応する０と１が入れ替えられる（ステップＳ５、Ｓ６）。そして、ＬＰＳに対応する遷移テーブル（AC_next_state_LPS_64）を引くことによって、ｓｔａｔｅの状態が更新される（ステップＳ７）。
【０００４】
ｓｙｍｂｏｌがＭＰＳであるときのｒａｎｇｅとｌｏｗの変化を図２（ｂ）に示す。ｓｙｍｂｏｌがＭＰＳであるとき、ｌｏｗは変化せず、ｒａｎｇｅにはＭＰＳの発生確率が設定される（ステップＳ２）。そして、ＭＰＳに対応する遷移テーブル（AC_next_state_MPS_64）を引くことによって、ｓｔａｔｅの状態が更新される（ステップＳ８）。
【０００５】
ｒａｎｇｅ＜０ｘ１００のときには、再正規化が行われ、ｒａｎｇｅとｌｏｗが拡大される（ステップＳ９、Ｓ１０）。図３は、再正規化を行うRenormalisation処理フローである（例えば、非特許文献１参照）。ｌｏｗ＜０ｘ１００のとき、出力は０に確定するため、０が１ビット出力される（ステップＳ１１、Ｓ１２、Ｓ１３）。０ｘ１００≦ｌｏｗ＜０ｘ２００のとき、その後の符号化状況により出力は０または１のどちらにもなる可能性がある。このため、未確定の出力の個数を示す変数（以下では、Ebits_to_followという。）がカウントアップされ、ｌｏｗから０ｘ１００が減算される（ステップＳ１１、Ｓ１２、Ｓ１４）。そして、０ｘ２００≦ｌｏｗのとき、出力は１に確定するため、１が１ビット出力され、ｌｏｗから０ｘ２００が減算される（ステップＳ１１、Ｓ１５）。その後、ｒａｎｇｅとｌｏｗは１ビット左論理シフトされ、２倍に拡大される（ステップＳ１６）。ｒａｎｇｅを２倍に拡大してもｒａｎｇｅ＜０ｘ１００のときはふたたびｒａｎｇｅとｌｏｗの拡大処理が行われ、ｒａｎｇｅ≧０ｘ１００になると再正規化が終了する（ステップＳ１０）。
【０００６】
図４は、確定した０または１を出力し、同時に未確定の出力を確定した出力に変換するput_one_bit_plus_outstanding(b)処理フローである（例えば、非特許文献１参照）。put_one_bit(b)は確定した０または１を１ビット出力する処理を行う（ステップＳ１７）。Ebits_to_follow＝０のときは未確定の出力がないため、処理を終了する（ステップＳ１８）。Ebits_to_follow＞０のとき、ステップＳ１７で出力した０または１を反転したビットをEbits_to_followに設定されている値の回数だけ出力する（ステップＳ１８、Ｓ１９）。
【０００７】
なお、ｓｙｍｂｏｌがＬＰＳであるとき、ｒａｎｇｅにはＬＰＳの発生確率（ｒＬＰＳ）が設定される。このとき、ＬＰＳの発生確率は０ｘ１００より小さいため、必ず再正規化される。一方、ｓｙｍｂｏｌがＭＰＳであるとき、ｒａｎｇｅからＬＰＳ発生確率が減算されることによってｒａｎｇｅ＜０ｘ１００となった場合にのみ再正規化される。
【０００８】
ｒａｎｇｅが２倍に拡大されても（ステップＳ１６）、ｒａｎｇｅ＜０ｘ１００であるときはふたたびｒａｎｇｅとｌｏｗを拡大する処理が行われる（ステップＳ１０）。このため、再正規化が終了したとき、ｒａｎｇｅの範囲は、０ｘ１００≦ｒａｎｇｅ≦０ｘ１ＦＥ（０ｘＦＦが２倍に拡大された値）となる。
【非特許文献１】H.264/AVC reference software ( JM 10.2 )
【発明の開示】
【発明が解決しようとする課題】
【０００９】
従来の技術による再正規化では、ｒａｎｇｅを２倍に拡大するごとに終了判定するため、一括してｒａｎｇｅとｌｏｗを拡大できず、高速に算術符号化を行うことができなかった。また、確定した０または１が出力されると、それを反転したものをEbits_to_followに設定されている値の回数だけ出力することによって未確定出力を確定出力に変換していたため、変換処理が複雑であった。
【課題を解決するための手段】
【００１０】
第１発明の２値算術符号化装置は、符号化の状態が２値信号系列の存在区間の幅と下端で表され、再正規化により該存在区間の幅と下端が１ビットからｎビットまで左論理シフトされて拡大される可能性がある２値算術符号化装置であって、拡大される可能性がある１ビットからｎビットまでの個々のシフト数に対応して設けられ、０、１、または未確定の３種類のいずれかのビット出力と、拡大された存在区間の下端の値が出力されるｎ個の存在区間下端拡大部と、再正規化による該存在区間の下端のシフト数がａビット（１≦ａ≦ｎの整数）であるとき、１ビットからａビットまでのシフト数に対応する前記存在区間下端拡大部からのビット出力を集めるビット出力集約部と、該ａビットのシフト数に対応する前記存在区間下端拡大部から出力される存在区間の下端を選択する存在区間下端選択部とを有することを特徴とする。
【００１１】
第２発明の２値算術符号化装置は、請求項１記載の発明において、前記ビット出力集約部から出力される個々のビット出力が未確定のときビット１を設定し、０または１のときビット０を設定することによってビット系列Ｓを作成し、かつ、前記ビット出力集約部から出力される個々のビット出力が１のときビット１を設定し、０または未確定のときビット０を設定することによってビット系列Ｃを作成し、該ビット系列Ｓを１ビット右論理シフトして該ビット系列Ｃと加算することによって、未確定が含まれるビット出力系列を確定したビット出力系列に変換するビット出力変換部を有することを特徴とする。
【００１２】
第３発明の２値算術符号化装置は、動画像符号化規格Ｈ．２６４におけるＣＡＢＡＣに準拠した２値算術符号化装置であって、拡大される可能性がある１ビットから７ビットまでの個々のシフト数に対応して設けられ、０、１、または未確定の３種類のいずれかのビット出力と、拡大された存在区間の下端の値が出力される７個の存在区間下端拡大部と、再正規化による該存在区間の下端のシフト数がａビット（１≦ａ≦７の整数）であるとき、１ビットからａビットまでのシフト数に対応する前記存在区間下端拡大部からのビット出力を集めるビット出力集約部と、該ａビットのシフト数に対応する前記存在区間下端拡大部から出力される存在区間の下端を選択する存在区間下端選択部と、前記ビット出力集約部から出力される個々のビット出力が未確定のときビット１を設定し、０または１のときビット０を設定することによってビット系列Ｓを作成し、かつ、前記ビット出力集約部から出力される個々のビット出力が１のときビット１を設定し、０または未確定のときビット０を設定することによってビット系列Ｃを作成し、該ビット系列Ｓを１ビット右論理シフトして該ビット系列Ｃと加算することによって、未確定が含まれるビット出力系列を確定したビット出力系列に変換するビット出力変換部とを有することを特徴とする。
【発明の効果】
【００１３】
第１の発明によれば、再正規化のシフト数が分かれば一括してｒａｎｇｅとｌｏｗを拡大できる。一方、シフト数は、ｒａｎｇｅについてＭＳＢから下位ビット側に向けて連続する０の数を検出することによって算出することができる。このため、一括してｒａｎｇｅとｌｏｗを拡大できるという効果がある。
【００１４】
また、第２の発明によれば、２つのビット出力系列を加算するという単純な方法で未確定が含まれるビット出力系列を一括して確定したビット出力系列に変換することができる。
【００１５】
第３の発明によれば、一括してｒａｎｇｅとｌｏｗを拡大でき、更に未確定が含まれるビット出力系列を一括して確定したビット出力系列に変換することができるため、高速に２値算術符号化を行うことができる。
【発明を実施するための最良の形態】
【００１６】
Ｈ．２６４におけるＣＡＢＡＣに準拠した算術符号化装置では、ｌｏｗのビット幅は１０ビットである。このため、２値算術符号化の過程でｌｏｗの値が０ｘ３ＦＦを越えることはない。
【００１７】
本発明は、２値算術符号化の過程でｌｏｗのとり得る値の範囲が所定の範囲内に制限されるという条件の下で、再正規化を高速に行う技術を提供するものである。
【実施例１】
【００１８】
本実施例では、２値算術符号化の過程でｌｏｗの値が０ｘ３ＦＦを越えることはなく、また、ｒａｎｇｅのビット幅は９ビットであるものとする。１回目のｌｏｗの拡大処理を以下に示す。
【００１９】
ｌｏｗ＜０ｘ１００のとき、ｌｏｗの上位２ビット＝０ｂ００（０ｂは、２進数であることを示す。以下、同じ。）である。そこで、ｌｏｗの上位２ビットを調べて０ｂ００であれば、２値算術符号化の状態として０を出力し、次式を実行する（ステップＳ１３に対応）。
【００２０】
low = low
【００２１】
このとき、ｌｏｗの上位２ビット＝０ｂ００であり、１ビット左論理シフト（ステップＳ１６）後にｌｏｗのＭＳＢ＝０となる。
【００２２】
０ｘ１００≦ｌｏｗ＜０ｘ２００のとき、ｌｏｗの上位２ビット＝０ｂ０１である。そこで、ｌｏｗの上位２ビットを調べて０ｂ０１であれば、２値算術符号化の状態として未確定であることを出力し、次式を実行する（ステップＳ１４に対応）。
【００２３】
low = low - 0x100
【００２４】
このとき、ｌｏｗの上位２ビット＝０ｂ００であり、１ビット左論理シフト（ステップＳ１６）後にｌｏｗのＭＳＢ＝０となる。
【００２５】
０ｘ２００≦ｌｏｗ＜０ｘ３００のとき、ｌｏｗの上位２ビット＝０ｂ１０である。そこで、ｌｏｗの上位２ビットを調べて０ｂ１０であれば、２値算術符号化の状態として１を出力し、次式を実行する（ステップＳ１５に対応）。
【００２６】
low = low - 0x200
【００２７】
このとき、ｌｏｗの上位２ビット＝０ｂ００であり、１ビット左論理シフト（ステップＳ１６）後にｌｏｗのＭＳＢ＝０となる。
【００２８】
０ｘ３００≦ｌｏｗ＜０ｘ４００のとき、ｌｏｗの上位２ビット＝０ｂ１１である。そこで、ｌｏｗの上位２ビットを調べて０ｂ１１であれば、２値算術符号化の状態として１を出力し、次式を実行する（ステップＳ１５に対応）。
【００２９】
low = low - 0x200
【００３０】
このとき、ｌｏｗの上位２ビット＝０ｂ０１であり、１ビット左論理シフト（ステップＳ１６）後にｌｏｗのＭＳＢ＝１となる。
【００３１】
上記１回目のｌｏｗの拡大処理において、１ビット左論理シフト（ステップＳ１６）後にｌｏｗのＭＳＢ＝１となるのは、再正規化を開始する前にｌｏｗの上位２ビット＝０ｂ１１であるときのみであり、その他のときは１ビット左論理シフト（ステップＳ１６）後にｌｏｗのＭＳＢ＝０となる。すなわち、ステップＳ１３、Ｓ１４、Ｓ１５、及びＳ１６を実行しなくても、再正規化が開始される前のｌｏｗの上位２ビットを調べれば、ｌｏｗの拡大処理が１回実行された後にそのＭＳＢが０または１のいずれになるか知ることができる。
【００３２】
ここで、上記の通り１回のｌｏｗの拡大処理における２値算術符号化の出力の状態は０、１、または未確定の３種類ある。そこで、本明細書と特許請求の範囲では、２値算術符号化の出力の状態をビット出力が０、１、または未確定であると表現する。
【００３３】
０ｘ０４０≦ｒａｎｇｅ＜０ｘ０８０のとき、ｒａｎｇｅを２倍に拡大しても（ステップＳ１６）、ｒａｎｇｅ＜０ｘ１００である。このとき、２回目のｌｏｗの拡大処理が行われる（ステップＳ１０）。ここで、上記の通り再正規化が開始される前のｌｏｗの上位２ビットを調べれば１回目にｌｏｗの拡大処理が実行された後のＭＳＢを知ることができることに着目すれば、１回目と２回目のｌｏｗの拡大処理を並列に行うことができる。
【００３４】
２回目のｌｏｗの拡大処理を以下に示す。
【００３５】
再正規化が開始される前のｌｏｗの上位２ビット≠０ｂ１１、かつ、ｌｏｗの上位から３ビット目＝０ｂ０のとき、ビット出力は０である（ステップＳ１３に対応）。このとき、左論理シフト（ステップＳ１６）が行われた後にｌｏｗのＭＳＢ＝０となる。
【００３６】
再正規化が開始される前のｌｏｗの上位２ビット≠０ｂ１１、かつ、ｌｏｗの上位から３ビット目＝０ｂ１のとき、ビット出力は未確定である（ステップＳ１４に対応）。このとき、左論理シフト（ステップＳ１６）が行われた後にｌｏｗのＭＳＢ＝０となる。
【００３７】
再正規化が開始される前のｌｏｗの上位２ビット＝０ｂ１１、かつ、ｌｏｗの上位から３ビット目＝０ｂ０のとき、ビット出力は１である（ステップＳ１５に対応）。このとき、左論理シフト（ステップＳ１６）が行われた後にｌｏｗのＭＳＢ＝０となる。
【００３８】
再正規化が開始される前のｌｏｗの上位２ビット＝０ｂ１１、かつ、ｌｏｗの上位から３ビット目＝０ｂ１のとき、ビット出力は１である（ステップＳ１５に対応）。このとき、左論理シフト（ステップＳ１６）が行われた後にｌｏｗのＭＳＢ＝１となる。従って、ｌｏｗの拡大処理が２回行われた後で、ｌｏｗのＭＳＢ＝１となるのは、再正規化が開始される前にｌｏｗの上位３ビット＝０ｂ１１１であったときのみである。
【００３９】
以上のように、ｌｏｗの拡大処理が２回行われるとき、再正規化が開始される前のｌｏｗの上位３ビットを調べれば、１回目のｌｏｗの拡大処理の内容とは関係なく、２回目のｌｏｗの拡大処理の内容を独立して決定することができる。
【００４０】
ｌｏｗの拡大処理が３回以上行われるときも同様であって、ｌｏｗの拡大処理がｎ回行われるとき、再正規化が開始される前のｌｏｗの上位（ｎ＋１）ビットを調べれば、ｎ回目のｌｏｗの拡大処理の内容を決定することができる。
【００４１】
ｎ回目のｌｏｗの拡大処理を以下に示す。
【００４２】
再正規化が開始される前のｌｏｗの上位ｎビットの中に少なくても１ビット０が含まれており、かつ、ｌｏｗの上位から（ｎ＋１）ビット目＝０ｂ０のとき、ビット出力は０である（ステップＳ１３に対応）。このとき、左論理シフト（ステップＳ１６）が行われた後にｌｏｗのＭＳＢ＝０となる。
【００４３】
再正規化が開始される前のｌｏｗの上位ｎビットの中に少なくても１ビット０が含まれており、かつ、ｌｏｗの上位から（ｎ＋１）ビット目＝０ｂ１のとき、ビット出力は未確定である（ステップＳ１４に対応）。このとき、左論理シフト（ステップＳ１６）が行われた後にｌｏｗのＭＳＢ＝０となる。
【００４４】
再正規化が開始される前のｌｏｗの上位ｎビットが全て１であり、かつ、ｌｏｗの上位から（ｎ＋１）ビット目＝０ｂ０のとき、ビット出力は１である（ステップＳ１５に対応）。このとき、左論理シフト（ステップＳ１６）が行われた後にｌｏｗのＭＳＢ＝０となる。
【００４５】
再正規化が開始される前のｌｏｗの上位（ｎ＋１）ビットが全て１のとき、ビット出力は１である（ステップＳ１５に対応）。このとき、左論理シフト（ステップＳ１６）が行われた後にｌｏｗのＭＳＢ＝１となる。
【００４６】
以上のように、再正規化が開始される前のｌｏｗの上位（ｎ＋１）ビットを調べれば、ｎ回目のｌｏｗの拡大処理の内容を決定することができる。
【００４７】
本発明による再正規化回路のブロック図を図５に示す。ｒａｎｇｅ≧０ｘ１００のとき再正規化が終了するものとする。この場合、正規化開始前のｒａｎｇｅの値が０ｘ０８０≦ｒａｎｇｅ＜０ｘ１００のときには、ｒａｎｇｅとｌｏｗの拡大処理が１回のみ行われる。ｒａｎｇｅは９ビットであるため、このとき、ｒａｎｇｅの上位２ビット＝０ｂ０１である。また、正規化開始前のｒａｎｇｅの値が０ｘ０４０≦ｒａｎｇｅ＜０ｘ０８０のときにはｒａｎｇｅとｌｏｗの拡大処理が２回行われる。このとき、ｒａｎｇｅの上位３ビット＝０ｂ００１である。正規化開始前のｒａｎｇｅの値が０ｘ００１≦ｒａｎｇｅ＜０ｘ００２のときにはｒａｎｇｅとｌｏｗの拡大処理が８回行われる。このとき、ｒａｎｇｅの上位９ビット＝０ｂ００００００００１であり、これはｒａｎｇｅのビット幅と一致する。ｒａｎｇｅ＜０ｘ００１となることはなく、ｌｏｗの拡大処理は最大８種類である。
【００４８】
本発明では、ｌｏｗの拡大処理を一括して行う。１回目から８回目までの各ｌｏｗの拡大処理を並列に行う回路が１ビットｌｏｗ拡大回路３から８ビットｌｏｗ拡大回路１０である。ｉビットｌｏｗ拡大回路では、再正規化が開始される前のｌｏｗの上位（ｉ＋１）ビットを調べて処理内容を決定する。個々のｉビットｌｏｗ拡大回路からは、０、１、または未確定の３種類のいずれかのビット出力、及びｉ回目のｌｏｗの拡大処理に対応するｌｏｗが出力される。
【００４９】
零検出回路２は、ｒａｎｇｅについてＭＳＢから下位ビット側に向けて、最大８ビットまで連続する０を検出する。零検出回路２によって検出された連続する０の数がａ個（１≦ａ≦８の整数）であるとき、ビット出力集約回路１１は１ビットｌｏｗ拡大回路３からａビットｌｏｗ拡大回路までのビット出力を集める。（ａ＋１）ビットｌｏｗ拡大回路から８ビットｌｏｗ拡大回路１０までのビット出力はビット出力集約回路１１によって捨てられる。これは、再正規化によってｌｏｗがａビット左論理シフトされて拡大されるとき、１ビットからａビットまでのシフト数に対応するビット出力だけを有効とし、（ａ＋１）ビットから８ビットまでのシフト数に対応するビット出力を無効とすることを意味する。ｌｏｗ選択回路１２は、零検出回路２によって０と検出されたビットの中で最下位のビットに対応するａビットｌｏｗ拡大回路から出力されるｌｏｗを選択する。一方、ｒａｎｇｅについては、ｒａｎｇｅシフト回路１でｒａｎｇｅをａビット左論理シフトすることによって、再正規化されたｒａｎｇｅが算出される。
【００５０】
なお、ＣＡＢＡＣでは、ＬＰＳの発生確率の最小値は０ｘ００２、最大値は０ｘ０Ｆ０と規定されている。ここで、入力したｓｙｍｂｏｌがＬＰＳであるとき、ｒａｎｇｅにはＬＰＳの発生確率が設定される。このため、ＬＰＳが入力したとき、ｒａｎｇｅの最小値は０ｘ００２となる。一方、入力したｓｙｍｂｏｌがＭＰＳであるとき、ｒａｎｇｅにはＭＰＳの発生確率（＝ｒａｎｇｅ−ＬＰＳ発生確率）が設定される。このため、ＭＰＳが入力したとき、ｒａｎｇｅは少なくとも次の値以上となる。
【００５１】
正規化終了時のrangeの最小値 - LPS発生確率の最大値 = 0x100 - 0x0F0 = 0x010
【００５２】
従って、ｒａｎｇｅの最小値は０ｘ００２であって、０ｘ００１≦ｒａｎｇｅ＜０ｘ００２となることはない。このため、ＣＡＢＡＣでは、零検出回路２は最大７ビットまで連続する０を検出できれば良く、また８ビットｌｏｗ拡大回路１０は不要である。
【実施例２】
【００５３】
２値算術符号化の過程においてｌｏｗが常に０ｘ２ＦＦ以下に保たれるようにｓｔａｔｅの遷移テーブル（AC_next_state_LPS64、AC_next_state_MPS64）とＬＰＳの発生確率テーブル（rLPS_table_64x4）を設計することも可能である。ｌｏｗが常に０ｘ２ＦＦ以下という条件が満たされるとき、ｌｏｗの拡大処理は実施例１よりも簡単になる。
【００５４】
本実施例では、ｌｏｗの値は必ず０ｘ２ＦＦ以下となるように、ｓｔａｔｅの遷移テーブルとＬＰＳの発生確率テーブルが設計されており、またｒａｎｇｅのビット幅は９ビットであるものとする。１回目のｌｏｗの拡大処理を以下に示す。
【００５５】
ｌｏｗ＜０ｘ１００のとき、ｌｏｗの上位２ビット＝０ｂ００である。そこで、ｌｏｗの上位２ビットを調べて０ｂ００であれば、ビット出力は０であり、次式を実行する（ステップＳ１３に対応）。
【００５６】
low = low
【００５７】
このとき、ｌｏｗの上位２ビット＝０ｂ００であり、１ビット左論理シフト（ステップＳ１６）後にｌｏｗのＭＳＢ＝０となる。
【００５８】
０ｘ１００≦ｌｏｗ＜０ｘ２００のとき、ｌｏｗの上位２ビット＝０ｂ０１である。そこで、ｌｏｗの上位２ビットを調べて０ｂ０１であれば、ビット出力は未確定であり、次式を実行する（ステップＳ１４に対応）。
【００５９】
low = low - 0x100
【００６０】
このとき、ｌｏｗの上位２ビット＝０ｂ００であり、１ビット左論理シフト（ステップＳ１６）後にｌｏｗのＭＳＢ＝０となる。
【００６１】
０ｘ２００≦ｌｏｗ＜０ｘ３００のとき、ｌｏｗの上位２ビット＝０ｂ１０である。そこで、ｌｏｗの上位２ビットを調べて０ｂ１０であれば、ビット出力は１であり、次式を実行する（ステップＳ１５に対応）。
【００６２】
low = low - 0x200
【００６３】
このとき、ｌｏｗの上位２ビット＝０ｂ００であり、１ビット左論理シフト（ステップＳ１６）後にｌｏｗのＭＳＢ＝０となる。
【００６４】
上記１回目のｌｏｗの拡大処理の結果は必ずｌｏｗ＜０ｘ２００となる。従って、２回目のｌｏｗの拡大処理は以下のようになる。
【００６５】
ｌｏｗ＜０ｘ１００のとき、ｌｏｗの上位から２ビット目、すなわち正規化開始前のｌｏｗの上位から３ビット目を調べて０であれば、ビット出力は０である（ステップＳ１３に対応）。このとき、１ビット左論理シフト（ステップＳ１６）後にｌｏｗのＭＳＢ＝０となる。
【００６６】
０ｘ１００≦ｌｏｗ＜０ｘ２００のとき、ｌｏｗの上位から２ビット目、すなわち正規化開始前のｌｏｗの上位から３ビット目を調べて１であれば、ビット出力は未確定である（ステップＳ１４に対応）。このとき、１ビット左論理シフト（ステップＳ１６）後にｌｏｗのＭＳＢ＝０となる。
【００６７】
このように、２回目のｌｏｗの拡大処理の結果も必ずｌｏｗ＜０ｘ２００となる。同様に、３回目以降のｌｏｗの拡大処理の結果もｌｏｗ＜０ｘ２００となることは明らかである。従って、１回目のｌｏｗの拡大処理を除いて、正規化開始前のｌｏｗの上位から（ｎ＋１）ビット目を調べれば、ｎ回目のｌｏｗの拡大処理の内容を決定することができる。
【００６８】
ｎ回目のｌｏｗの拡大処理を以下に示す。
【００６９】
再正規化が開始される前のｌｏｗの上位から（ｎ＋１）ビット目を調べて０であれば、ビット出力は０である（ステップＳ１３に対応）。
【００７０】
再正規化が開始される前のｌｏｗの上位から（ｎ＋１）ビット目を調べて１であれば、ビット出力は未確定である（ステップＳ１４に対応）。
【００７１】
以上のように、ｌｏｗの拡大処理を実施例１よりも簡単に行うことができる。１ビットｌｏｗ拡大回路３はｌｏｗの上位２ビットを調べることにより処理内容を決定でき、ビット出力は０、１、または未確定の３種類である。１ビットｌｏｗ拡大回路３を除き、ｉビットｌｏｗ拡大回路は、再正規化が開始される前のｌｏｗの（ｉ＋１）ビット目を調べることにより処理内容を決定でき、ビット出力は０または未確定の２種類である。
【００７２】
なお、実施例１と実施例２では、ｒａｎｇｅとｌｏｗのビット幅が９ビットと１０ビットの場合について説明したが、本発明ではｒａｎｇｅとｌｏｗのビット幅は９ビットと１０ビットに限られない。
【実施例３】
【００７３】
H.264/AVC reference softwareに記述されている正規化の方法では、図３に示すように、ｌｏｗの拡大処理において出力が０または１のいずれにもなる可能性があるときはEbits_to_followがカウントアップされる（ステップＳ１４）。そして、確定した０または１を出力するとき（ステップＳ１３、Ｓ１５）、図４に示すように、この確定した０または１を反転したビットがEbits_to_followに設定されている値の回数だけ出力される（ステップＳ１８、Ｓ１９）。
【００７４】
一方、実施例１または実施例２に示す方法で正規化を行うと、ビット出力として０、１、または未確定の３種類の状態が出力される。本実施例では、未確定を含むビット出力を０と１のみの確定したビット出力に高速に変換する方法を示す。
【００７５】
未確定という状態をＳで表すと、以下のように変換すれば、図４の処理フローと同じ結果を得ることができる。
【００７６】
出力が０と確定したとき、SSS……SS0を0111……11に変換する。一方、出力が１と確定したときは、SSS……SS1を1000……00に変換する。
【００７７】
本発明では、この変換処理を加算により実現する。本発明における確定したビット出力への変換処理を図６に示す。図６（ａ）は出力が０に確定した場合である。本発明では、Ｓを１とみなし、Ｓの数だけ連続する１のビット列のＬＳＢに０を加算することにより、出力が０と確定したときの変換処理を行う。
【００７８】
図６（ｂ）は出力が１に確定した場合である。出力が１と確定した場合には、Ｓの数だけ連続する１のビット列のＬＳＢに１を加算することにより変換処理を行う。
【００７９】
具体的には、ビット出力が未確定のときビット１を設定し、ビット出力が０または１のときビット０を設定することによってビット系列Ｓを作成する。また、ビット出力が１であるときビット１を設定し、ビット出力が０または未確定のときビット０を設定することによってビット系列Ｃを作成する。すなわち、ビット出力が未確定のとき（Ｓ，Ｃ）＝（１，０）、ビット出力が０のとき（Ｓ，Ｃ）＝（０，０）、ビット出力が１のとき（Ｓ，Ｃ）＝（０，１）を設定する。そして、ビット系列Ｓを１ビット右論理シフトしてビット系列Ｃと加算することにより、一括して確定した出力ビット系列に変換する。
【００８０】
ただし、実際の加算器のビット長は有限であるため、一括して変換できるビット数は加算器のビット長に依存する。８ビットごとに一括して変換する回路を図７に示す。この回路を用いて、次の１６ビットの出力ビット系列を８ビットごとに一括して変換する例を図８に示す。
【００８１】
SSSS S1SS S1SS 0SSS → 1000 0010 0001 1SSS
【００８２】
ビット系列Ｓとビット系列Ｃはそれぞれ以下のようになる。
【００８３】
S = 1111 1011 1011 0111
【００８４】
C = 0000 0100 0100 0000
【００８５】
この場合、８ビット加算器１３，１４を用いる。まず、８ビット加算器１４を用いてビット系列Ｓの上位側７ビットの先頭にビット０を付加した「0111 1101」と、ビット系列Ｃの上位側８ビット「0000
0100」を加算する。次に、その加算結果を８ビット加算器１３に設定する。図８では、ビット系列Ｓの上位側８ビットに加算結果を設定し、ビット系列Ｃの上位側８ビットは全て０としたが、ビット系列Ｓの上位側８ビットは全て０とし、ビット系列Ｃの上位側８ビットに加算結果を設定しても良い。そして、再度８ビット加算器１４を用いてビット系列Ｓの８ビット目から１５ビット目の「1101
1011」と、ビット系列Ｃの下位側８ビット「0100 0000」を加算する。そのとき、キャリが８ビット加算器１４から出力され、８ビット加算器１３のＬＳＢに加算される。これにより、上位側８ビットについて出力が確定する。しかし、下位側８ビットについては最後の３ビットが下位側からのキャリの伝播により反転する可能性があり、まだ確定していない。下位側８ビットについては、その加算結果を８ビット加算器１３に設定し、更にその下位８ビットのビット系列ＳとＣについて８ビット加算器１４で同様の計算を行うことにより確定する。なお、図８のビット系列Ｓは１ビット右シフトされるため、最後の１ビットが余るが、この余った１ビットは、下位のビット系列Ｓの先頭に付加する。
【００８６】
ただし、８ビット加算器１４に入力される８ビット全部のビット出力が未確定である場合が問題となる。ビット系列Ｓの８ビットは全て１、かつ、ビット系列Ｃの８ビットは全て０の場合、下位側からキャリが入力しないとき、８ビット加算器１３へのキャリは発生しない。一方、下位側からキャリが伝播してきたときは、８ビット加算器１３へのキャリが発生する。この問題を解決するために、本発明では、０ｘＦＦ検出回路２０でビット系列Ｓの８ビットが全て１であることを検出し、また、ＬＳＢ０検出回路２１でビット系列Ｃの８ビットの中の最下位ビットが０であることを検出する。そして、ビット系列Ｓの８ビットが全て１、かつ、ビット系列Ｃの８ビットの中の最下位ビットが０という条件が成立した場合、その８ビットをビット系列ＳとＣの両方から除去する。ここで、ビット系列Ｃの８ビットの中の最下位ビットが０という条件が必要となる理由は、ビット系列Ｓは１ビット右論理シフトされているため、ビット系列Ｓの８ビットが全て１であっても、ビット系列Ｃの８ビットの中の最下位ビットは１である可能性があるためである。その後、８ビット加算器１４に入力される下位のビット系列ＳとＣについてビット系列Ｓの８ビット中に少なくても１ビットは０が含まれるか、または、ビット系列Ｃの８ビットの中の最下位ビットが１であるといういずれかの条件が成立したとき、８ビット加算器１４からキャリが出力される場合には０ｘ００／０ｘＦＦ挿入回路１７で出力ビット系列に０ｘ００を挿入し、８ビット加算器１４からキャリが出力されない場合には出力ビット系列に０ｘＦＦを挿入する。
【００８７】
なお、実施例３では、８ビット加算器を２個用いたが、２個の加算器のビット長が同じであれば良く、例えば１６ビット加算器を２個用いても良い。
【００８８】
また、本明細書と特許請求の範囲では、ｒａｎｇｅとｌｏｗを拡大する処理を左論理シフトで行うと記載したが、左論理シフトと等しい結果が得られる演算であれば良く、拡大処理を乗算により実現しても良い。
【産業上の利用可能性】
【００８９】
本発明は、動画像の圧縮や音声の圧縮等データを圧縮する分野で利用価値が高い。
【図面の簡単な説明】
【００９０】
【図１】ＣＡＢＡＣに準拠した算術符号化を行うBiari_encode_symbol処理フローを示す図である。（背景技術）
【図２】ｓｙｍｂｏｌがＬＰＳおよびＭＰＳであるときのｒａｎｇｅとｌｏｗの変化を示した説明図である。（背景技術）
【図３】ＣＡＢＡＣに準拠した算術符号化における再正規化を行うRenormalisation処理フローを示す図である。（背景技術）
【図４】確定した０または１を出力し、同時に未確定の出力を確定した出力に変換するput_one_bit_plus_outstanding(b)処理フローを示す図である。（背景技術）
【図５】本発明による再正規化回路のブロック図である。（実施例１）
【図６】本発明における未確定を含むビット出力を確定したビット出力へ変換する例を示す図である。（実施例３）
【図７】本発明における未確定を含むビット出力系列を８ビットごとに一括して確定したビット出力系列へ変換する回路のブロック図である。（実施例３）
【図８】未確定を含む１６ビットのビット出力系列を８ビットごとに一括して確定したビット出力系列へ変換する例を示す図である。（実施例３）
【符号の説明】
【００９１】
１    ｒａｎｇｅシフト回路
２    零検出回路
３    １ビットｌｏｗ拡大回路
４    ２ビットｌｏｗ拡大回路
５    ３ビットｌｏｗ拡大回路
６    ４ビットｌｏｗ拡大回路
７    ５ビットｌｏｗ拡大回路
８    ６ビットｌｏｗ拡大回路
９    ７ビットｌｏｗ拡大回路
１０    ８ビットｌｏｗ拡大回路
１１    ビット出力集約回路
１２    ｌｏｗ選択回路
１３、１４    ８ビット加算器
１５、１６、１８、１９    ８ビットレジスタ
１７    ０ｘ００／０ｘＦＦ挿入回路
２０    ０ｘＦＦ検出回路
２１    ＬＳＢ０検出回路
【図１】
2007300444.tif 000003
【図２】
2007300444.tif 000004
【図３】
2007300444.tif 000005
【図４】
2007300444.tif 000006
【図５】
2007300444.tif 000007
【図６】
2007300444.tif 000008
【図７】
2007300444.tif 000009
【図８】
2007300444.tif 000010
【手続補正書】
【提出日】平成19年9月1日(2007.9.1)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
算術符号化の状態が２値信号系列の存在区間の幅と下端で表され、再正規化により当該存在区間の幅と下端が左論理シフトされて拡大される２値算術符号化装置であって、
前記存在区間の幅について、最上位ビットから下位側のビットに向けてｍビット（ｍは整数）目まで、最上位ビットから連続する０の数を検出し、当該検出された０の数を検出拡大処理回数とする零検出部と、
前記存在区間の幅を前記検出拡大処理回数に応じたシフト数だけ左論理シフトし、拡大された存在区間の幅を生成する存在区間幅シフト部と、
１回からｍ回までの想定される拡大処理の回数に対応して設けられ、前記存在区間の下端における最上位ビットから下位側のビットに向けて、当該想定される拡大処理の回数に１を加えた数で指定される位置のビットまでのビットに応じて決定される０、１、または未確定の３種類のいずれかの中間ビット出力と、当該想定される拡大処理の回数に応じたシフト数だけ左論理シフトされて拡大された想定される存在区間の下端とが出力されるｍ個の存在区間下端拡大部と、
前記想定される拡大処理の回数が１回から前記検出拡大処理回数までに対応する前記存在区間下端拡大部の中間ビット出力を集めるビット出力集約部と、
前記想定される拡大処理の回数が前記検出拡大処理回数に等しい前記存在区間下端拡大部から出力される前記想定される存在区間の下端を選択し、拡大された存在区間の下端として出力する存在区間下端選択部と、
前記ビット出力集約部から出力される前記中間ビット出力が、未確定のときビットとして１を設定し、０または１のときビットとして０を設定することによって第１のビット系列を作成し、かつ、前記ビット出力集約部から出力される個々の前記中間ビット出力が、１のときビットとして１を設定し、０または未確定のときビットとして０を設定することによって第２のビット系列を作成し、前記第１のビット系列を１ビット右論理シフトして前記第２のビット系列と加算し、確定したビット出力を生成するビット出力変換部と
を有する２値算術符号化装置。
【請求項２】
動画像符号化規格Ｈ．２６４で規定されるコンテキスト適応型２値算術符号化（ＣＡＢＡＣ）に準拠し、前記ｍが７に等しい請求項１に記載の２値算術符号化装置。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、算術符号化装置に関するものであり、特に、動画像符号化規格Ｈ．２６４におけるＣＡＢＡＣ
（ Ｃｏｎｔｅｘｔ−ｂａｓｅｄ  Ａｄａｐｔｉｖｅ  Ｂｉｎａｒｙ  Ａｒｉｔｈｍｅｔｉｃ  Ｃｏｄｉｎｇ；コンテキスト適応型２値算術符号化方式） に準拠した算術符号化装置に適したものである。
【背景技術】
【０００２】
ＣＡＢＡＣでは多値のシンタックスエレメントを２値信号（０と１の信号）に変換し、この２値信号（以下、ｓｙｍｂｏｌという。）を算術符号化する。図１は、ＣＡＢＡＣに準拠した算術符号化を行うBiari_encode_symbol処理フローである（例えば、非特許文献１参照）。ＣＡＢＡＣでは、符号化の状態をｓｙｍｂｏｌ系列の存在区間の幅（以下、ｒａｎｇｅという。）と下端（以下、ｌｏｗという）で表す。ｒａｎｇｅとｌｏｗのビット幅はそれぞれ９ビットと１０ビットであり、スライスの先頭でｒａｎｇｅは０ｘ１ＦＥ（０ｘは、１６進数であることを示す。以下、同じ。）、ｌｏｗは０ｘ０００に初期化される。０と１のうち、発生確率の低い方がＬＰＳ（Ｌｅａｓｔ  Ｐｒｏｂａｂｌｅ  Ｓｙｍｂｏｌ）に割り当てられ、発生確率の高い方がＭＰＳ（Ｍｏｓｔ  Ｐｒｏｂａｂｌｅ  Ｓｙｍｂｏｌ）に割り当てられる。ＬＰＳの発生確率（ｒＬＰＳ）は、発生確率の状態を示す番号（以下、ｓｔａｔｅという。）とｒａｎｇｅによってテーブル（rLPS_table_64x4）を引くことにより求められる（ステップＳ１）。一方、ＭＰＳの発生確率は、ｒａｎｇｅからＬＰＳの発生確率（ｒＬＰＳ）を減算することで算出される（ステップＳ２）。
【０００３】
ｓｙｍｂｏｌがＬＰＳであるときのｒａｎｇｅとｌｏｗの変化を図２（ａ）に示す。ｓｙｍｂｏｌがＬＰＳであるとき、ＭＰＳの発生確率を加算することによってｌｏｗが更新され、ｒａｎｇｅにはＬＰＳの発生確率（ｒＬＰＳ）が設定される（ステップＳ４）。ｓｔａｔｅ＝０であれば、次の符号化状態における０と１の発生確率の大小が逆転すると予想されるため、ＭＰＳに対応する０と１が入れ替えられる（ステップＳ５、Ｓ６）。そして、ＬＰＳに対応する遷移テーブル（AC_next_state_LPS_64）を引くことによって、ｓｔａｔｅの状態が更新される（ステップＳ７）。
【０００４】
ｓｙｍｂｏｌがＭＰＳであるときのｒａｎｇｅとｌｏｗの変化を図２（ｂ）に示す。ｓｙｍｂｏｌがＭＰＳであるとき、ｌｏｗは変化せず、ｒａｎｇｅにはＭＰＳの発生確率が設定される（ステップＳ２）。そして、ＭＰＳに対応する遷移テーブル（AC_next_state_MPS_64）を引くことによって、ｓｔａｔｅの状態が更新される（ステップＳ８）。
【０００５】
ｒａｎｇｅ＜０ｘ１００のときには、再正規化が行われ、ｒａｎｇｅとｌｏｗが拡大される（ステップＳ９、Ｓ１０）。図３は、再正規化を行うRenormalisation処理フローである（例えば、非特許文献１参照）。ｌｏｗ＜０ｘ１００のとき、出力は０に確定するため、０が１ビット出力される（ステップＳ１１、Ｓ１２、Ｓ１３）。０ｘ１００≦ｌｏｗ＜０ｘ２００のとき、その後の符号化状況により出力は０または１のどちらにもなる可能性がある。このため、未確定の出力の個数を示す変数（以下では、Ebits_to_followという。）がカウントアップされ、ｌｏｗから０ｘ１００が減算される（ステップＳ１１、Ｓ１２、Ｓ１４）。そして、０ｘ２００≦ｌｏｗのとき、出力は１に確定するため、１が１ビット出力され、ｌｏｗから０ｘ２００が減算される（ステップＳ１１、Ｓ１５）。その後、ｒａｎｇｅとｌｏｗは１ビット左論理シフトされ、２倍に拡大される（ステップＳ１６）。ｒａｎｇｅを２倍に拡大してもｒａｎｇｅ＜０ｘ１００のときはふたたびｒａｎｇｅとｌｏｗの拡大処理が行われ、ｒａｎｇｅ≧０ｘ１００になると再正規化が終了する（ステップＳ１０）。
【０００６】
図４は、確定した０または１を出力し、同時に未確定の出力を確定した出力に変換するput_one_bit_plus_outstanding(b)処理フローである（例えば、非特許文献１参照）。put_one_bit(b)は確定した０または１を１ビット出力する処理を行う（ステップＳ１７）。Ebits_to_follow＝０のときは未確定の出力がないため、処理を終了する（ステップＳ１８）。Ebits_to_follow＞０のとき、ステップＳ１７で出力した０または１を反転したビットをEbits_to_followに設定されている値の回数だけ出力する（ステップＳ１８、Ｓ１９）。
【０００７】
なお、ｓｙｍｂｏｌがＬＰＳであるとき、ｒａｎｇｅにはＬＰＳの発生確率（ｒＬＰＳ）が設定される。このとき、ＬＰＳの発生確率は０ｘ１００より小さいため、必ず再正規化される。一方、ｓｙｍｂｏｌがＭＰＳであるとき、ｒａｎｇｅからＬＰＳ発生確率が減算されることによってｒａｎｇｅ＜０ｘ１００となった場合にのみ再正規化される。
【０００８】
ｒａｎｇｅが２倍に拡大されても（ステップＳ１６）、ｒａｎｇｅ＜０ｘ１００であるときはふたたびｒａｎｇｅとｌｏｗを拡大する処理が行われる（ステップＳ１０）。このため、再正規化が終了したとき、ｒａｎｇｅの範囲は、０ｘ１００≦ｒａｎｇｅ≦０ｘ１ＦＥ（０ｘＦＦが２倍に拡大された値）となる。
【非特許文献１】H.264/AVC reference software ( JM 10.2 )
【発明の開示】
【発明が解決しようとする課題】
【０００９】
従来の技術による再正規化では、ｒａｎｇｅを２倍に拡大するごとに終了判定するため、一括してｒａｎｇｅとｌｏｗを拡大できず、高速に算術符号化を行うことができなかった。また、確定した０または１が出力されると、それを反転したものを未確定の出力の数だけ出力することによって未確定出力を確定出力に変換していたため、変換処理が複雑であった。
【課題を解決するための手段】
【００１０】
本発明の２値算術符号化装置は、算術符号化の状態が２値信号系列の存在区間の幅と下端で表され、再正規化により当該存在区間の幅と下端が左論理シフトされて拡大される２値算術符号化装置であって、
前記存在区間の幅について、最上位ビットから下位側のビットに向けてｍビット（ｍは整数）目まで、最上位ビットから連続する０の数を検出し、当該検出された０の数を検出拡大処理回数とする零検出部と、
前記存在区間の幅を前記検出拡大処理回数に応じたシフト数だけ左論理シフトし、拡大された存在区間の幅を生成する存在区間幅シフト部と、
１回からｍ回までの想定される拡大処理の回数に対応して設けられ、前記存在区間の下端における最上位ビットから下位側のビットに向けて、当該想定される拡大処理の回数に１を加えた数で指定される位置のビットまでのビットに応じて決定される０、１、または未確定の３種類のいずれかの中間ビット出力と、当該想定される拡大処理の回数に応じたシフト数だけ左論理シフトされて拡大された想定される存在区間の下端とが出力されるｍ個の存在区間下端拡大部と、
前記想定される拡大処理の回数が１回から前記検出拡大処理回数までに対応する前記存在区間下端拡大部の中間ビット出力を集めるビット出力集約部と、
前記想定される拡大処理の回数が前記検出拡大処理回数に等しい前記存在区間下端拡大部から出力される前記想定される存在区間の下端を選択し、拡大された存在区間の下端として出力する存在区間下端選択部と、
前記ビット出力集約部から出力される前記中間ビット出力が、未確定のときビットとして１を設定し、０または１のときビットとして０を設定することによって第１のビット系列を作成し、かつ、前記ビット出力集約部から出力される個々の前記中間ビット出力が、１のときビットとして１を設定し、０または未確定のときビットとして０を設定することによって第２のビット系列を作成し、前記第１のビット系列を１ビット右論理シフトして前記第２のビット系列と加算し、確定したビット出力を生成するビット出力変換部と
を有する。
【００１１】
好ましくは、本発明の２値算術符号化装置は、動画像符号化規格Ｈ．２６４で規定されるコンテキスト適応型２値算術符号化（ＣＡＢＡＣ）に準拠し、前記ｍが７に等しい。
【発明の効果】
【００１２】
本発明によれば、一括してｒａｎｇｅとｌｏｗを拡大でき、高速に算術符号化を行うことができる。また、２つのビット出力系列を加算するという単純な方法で未確定が含まれるビット出力系列を一括して確定したビット出力系列に変換することができる。
【発明を実施するための最良の形態】
【００１３】
Ｈ．２６４におけるＣＡＢＡＣに準拠した算術符号化装置では、ｌｏｗのビット幅は１０ビットである。このため、２値算術符号化の過程でｌｏｗの値が０ｘ３ＦＦを越えることはない。
【００１４】
本発明は、２値算術符号化の過程でｌｏｗのとり得る値の範囲が所定の範囲内に制限されるという条件の下で、再正規化を高速に行う技術を提供するものである。
【００１５】
（第１の実施形態）
本実施形態では、２値算術符号化の過程でｌｏｗの値が０ｘ３ＦＦを越えることはなく、また、ｒａｎｇｅのビット幅は９ビットであるものとする。１回目のｌｏｗの拡大処理を以下に示す。
【００１６】
ｌｏｗ＜０ｘ１００のとき、ｌｏｗの上位２ビット＝０ｂ００（０ｂは、２進数であることを示す。以下、同じ。）である。そこで、ｌｏｗの上位２ビットを調べて０ｂ００であれば、２値算術符号化の状態として０を出力し、次式を実行する（ステップＳ１３に対応）。
【００１７】
low = low
【００１８】
このとき、ｌｏｗの上位２ビット＝０ｂ００であり、１ビット左論理シフト（ステップＳ１６）後にｌｏｗのＭＳＢ＝０となる。
【００１９】
０ｘ１００≦ｌｏｗ＜０ｘ２００のとき、ｌｏｗの上位２ビット＝０ｂ０１である。そこで、ｌｏｗの上位２ビットを調べて０ｂ０１であれば、２値算術符号化の状態として未確定であることを出力し、次式を実行する（ステップＳ１４に対応）。
【００２０】
low = low - 0x100
【００２１】
このとき、ｌｏｗの上位２ビット＝０ｂ００であり、１ビット左論理シフト（ステップＳ１６）後にｌｏｗのＭＳＢ＝０となる。
【００２２】
０ｘ２００≦ｌｏｗ＜０ｘ３００のとき、ｌｏｗの上位２ビット＝０ｂ１０である。そこで、ｌｏｗの上位２ビットを調べて０ｂ１０であれば、２値算術符号化の状態として１を出力し、次式を実行する（ステップＳ１５に対応）。
【００２３】
low = low - 0x200
【００２４】
このとき、ｌｏｗの上位２ビット＝０ｂ００であり、１ビット左論理シフト（ステップＳ１６）後にｌｏｗのＭＳＢ＝０となる。
【００２５】
０ｘ３００≦ｌｏｗ＜０ｘ４００のとき、ｌｏｗの上位２ビット＝０ｂ１１である。そこで、ｌｏｗの上位２ビットを調べて０ｂ１１であれば、２値算術符号化の状態として１を出力し、次式を実行する（ステップＳ１５に対応）。
【００２６】
low = low - 0x200
【００２７】
このとき、ｌｏｗの上位２ビット＝０ｂ０１であり、１ビット左論理シフト（ステップＳ１６）後にｌｏｗのＭＳＢ＝１となる。
【００２８】
上記１回目のｌｏｗの拡大処理において、１ビット左論理シフト（ステップＳ１６）後にｌｏｗのＭＳＢ＝１となるのは、再正規化を開始する前にｌｏｗの上位２ビット＝０ｂ１１であるときのみであり、その他のときは１ビット左論理シフト（ステップＳ１６）後にｌｏｗのＭＳＢ＝０となる。すなわち、ステップＳ１３、Ｓ１４、Ｓ１５、及びＳ１６を実行しなくても、再正規化が開始される前のｌｏｗの上位２ビットを調べれば、ｌｏｗの拡大処理が１回実行された後にそのＭＳＢが０または１のいずれになるか知ることができる。
【００２９】
ここで、上記の通り１回のｌｏｗの拡大処理における２値算術符号化の出力の状態は０、１、または未確定の３種類ある。そこで、本明細書と特許請求の範囲では、２値算術符号化の出力の状態をビット出力が０、１、または未確定であると表現する。
【００３０】
０ｘ０４０≦ｒａｎｇｅ＜０ｘ０８０のとき、ｒａｎｇｅを２倍に拡大しても（ステップＳ１６）、ｒａｎｇｅ＜０ｘ１００である。このとき、２回目のｌｏｗの拡大処理が行われる（ステップＳ１０）。ここで、上記の通り再正規化が開始される前のｌｏｗの上位２ビットを調べれば１回目にｌｏｗの拡大処理が実行された後のＭＳＢを知ることができることに着目すれば、１回目と２回目のｌｏｗの拡大処理を並列に行うことができる。
【００３１】
２回目のｌｏｗの拡大処理を以下に示す。
【００３２】
再正規化が開始される前のｌｏｗの上位２ビット≠０ｂ１１、かつ、ｌｏｗの上位から３ビット目＝０ｂ０のとき、ビット出力は０である（ステップＳ１３に対応）。このとき、左論理シフト（ステップＳ１６）が行われた後にｌｏｗのＭＳＢ＝０となる。
【００３３】
再正規化が開始される前のｌｏｗの上位２ビット≠０ｂ１１、かつ、ｌｏｗの上位から３ビット目＝０ｂ１のとき、ビット出力は未確定である（ステップＳ１４に対応）。このとき、左論理シフト（ステップＳ１６）が行われた後にｌｏｗのＭＳＢ＝０となる。
【００３４】
再正規化が開始される前のｌｏｗの上位２ビット＝０ｂ１１、かつ、ｌｏｗの上位から３ビット目＝０ｂ０のとき、ビット出力は１である（ステップＳ１５に対応）。このとき、左論理シフト（ステップＳ１６）が行われた後にｌｏｗのＭＳＢ＝０となる。
【００３５】
再正規化が開始される前のｌｏｗの上位２ビット＝０ｂ１１、かつ、ｌｏｗの上位から３ビット目＝０ｂ１のとき、ビット出力は１である（ステップＳ１５に対応）。このとき、左論理シフト（ステップＳ１６）が行われた後にｌｏｗのＭＳＢ＝１となる。従って、ｌｏｗの拡大処理が２回行われた後で、ｌｏｗのＭＳＢ＝１となるのは、再正規化が開始される前にｌｏｗの上位３ビット＝０ｂ１１１であったときのみである。
【００３６】
以上のように、ｌｏｗの拡大処理が２回行われるとき、再正規化が開始される前のｌｏｗの上位３ビットを調べれば、１回目のｌｏｗの拡大処理の内容とは関係なく、２回目のｌｏｗの拡大処理の内容を独立して決定することができる。
【００３７】
ｌｏｗの拡大処理が３回以上行われるときも同様であって、ｌｏｗの拡大処理がｎ回行われるとき、再正規化が開始される前のｌｏｗの上位（ｎ＋１）ビットを調べれば、ｎ回目のｌｏｗの拡大処理の内容を決定することができる。
【００３８】
ｎ回目のｌｏｗの拡大処理を以下に示す。
【００３９】
再正規化が開始される前のｌｏｗの上位ｎビットの中に少なくても１ビット０が含まれており、かつ、ｌｏｗの上位から（ｎ＋１）ビット目＝０ｂ０のとき、ビット出力は０である（ステップＳ１３に対応）。このとき、左論理シフト（ステップＳ１６）が行われた後にｌｏｗのＭＳＢ＝０となる。
【００４０】
再正規化が開始される前のｌｏｗの上位ｎビットの中に少なくても１ビット０が含まれており、かつ、ｌｏｗの上位から（ｎ＋１）ビット目＝０ｂ１のとき、ビット出力は未確定である（ステップＳ１４に対応）。このとき、左論理シフト（ステップＳ１６）が行われた後にｌｏｗのＭＳＢ＝０となる。
【００４１】
再正規化が開始される前のｌｏｗの上位ｎビットが全て１であり、かつ、ｌｏｗの上位から（ｎ＋１）ビット目＝０ｂ０のとき、ビット出力は１である（ステップＳ１５に対応）。このとき、左論理シフト（ステップＳ１６）が行われた後にｌｏｗのＭＳＢ＝０となる。
【００４２】
再正規化が開始される前のｌｏｗの上位（ｎ＋１）ビットが全て１のとき、ビット出力は１である（ステップＳ１５に対応）。このとき、左論理シフト（ステップＳ１６）が行われた後にｌｏｗのＭＳＢ＝１となる。
【００４３】
以上のように、再正規化が開始される前のｌｏｗの上位（ｎ＋１）ビットを調べれば、ｎ回目のｌｏｗの拡大処理の内容を決定することができる。
【００４４】
本発明による再正規化回路のブロック図を図５に示す。ｒａｎｇｅ≧０ｘ１００のとき再正規化が終了するものとする。この場合、正規化開始前のｒａｎｇｅの値が０ｘ０８０≦ｒａｎｇｅ＜０ｘ１００のときには、ｒａｎｇｅとｌｏｗの拡大処理が１回のみ行われる。ｒａｎｇｅは９ビットであるため、このとき、ｒａｎｇｅの上位２ビット＝０ｂ０１である。また、正規化開始前のｒａｎｇｅの値が０ｘ０４０≦ｒａｎｇｅ＜０ｘ０８０のときにはｒａｎｇｅとｌｏｗの拡大処理が２回行われる。このとき、ｒａｎｇｅの上位３ビット＝０ｂ００１である。正規化開始前のｒａｎｇｅの値が０ｘ００１≦ｒａｎｇｅ＜０ｘ００２のときにはｒａｎｇｅとｌｏｗの拡大処理が８回行われる。このとき、ｒａｎｇｅの上位９ビット＝０ｂ００００００００１であり、これはｒａｎｇｅのビット幅と一致する。ｒａｎｇｅ＜０ｘ００１となることはなく、ｌｏｗの拡大処理は最大８種類である。
【００４５】
本発明では、ｌｏｗの拡大処理を一括して行う。１回目から８回目までの各ｌｏｗの拡大処理を並列に行う回路が１ビットｌｏｗ拡大回路３から８ビットｌｏｗ拡大回路１０である。ｉビットｌｏｗ拡大回路では、再正規化が開始される前のｌｏｗの上位（ｉ＋１）ビットを調べて処理内容を決定する。個々のｉビットｌｏｗ拡大回路からは、０、１、または未確定の３種類のいずれかのビット出力、及びｉ回目のｌｏｗの拡大処理に対応するｌｏｗが出力される。
【００４６】
零検出回路２は、ｒａｎｇｅについてＭＳＢから下位ビット側に向けて、最大８ビットまで連続する０を検出する。零検出回路２によって検出された連続する０の数がａ個（１≦ａ≦８の整数）であるとき、ビット出力集約回路１１は１ビットｌｏｗ拡大回路３からａビットｌｏｗ拡大回路までのビット出力を集める。（ａ＋１）ビットｌｏｗ拡大回路から８ビットｌｏｗ拡大回路１０までのビット出力はビット出力集約回路１１によって捨てられる。これは、再正規化によってｌｏｗがａビット左論理シフトされて拡大されるとき、１ビットからａビットまでのシフト数に対応するビット出力だけを有効とし、（ａ＋１）ビットから８ビットまでのシフト数に対応するビット出力を無効とすることを意味する。ｌｏｗ選択回路１２は、零検出回路２によって０と検出されたビットの中で最下位のビットに対応するａビットｌｏｗ拡大回路から出力されるｌｏｗを選択する。一方、ｒａｎｇｅについては、ｒａｎｇｅシフト回路１でｒａｎｇｅをａビット左論理シフトすることによって、再正規化されたｒａｎｇｅが算出される。
【００４７】
なお、ＣＡＢＡＣでは、ＬＰＳの発生確率の最小値は０ｘ００２、最大値は０ｘ０Ｆ０と規定されている。ここで、入力したｓｙｍｂｏｌがＬＰＳであるとき、ｒａｎｇｅにはＬＰＳの発生確率が設定される。このため、ＬＰＳが入力したとき、ｒａｎｇｅの最小値は０ｘ００２となる。一方、入力したｓｙｍｂｏｌがＭＰＳであるとき、ｒａｎｇｅにはＭＰＳの発生確率（＝ｒａｎｇｅ−ＬＰＳ発生確率）が設定される。このため、ＭＰＳが入力したとき、ｒａｎｇｅは少なくとも次の値以上となる。
【００４８】
正規化終了時のrangeの最小値 - LPS発生確率の最大値 = 0x100 - 0x0F0 = 0x010
【００４９】
従って、ｒａｎｇｅの最小値は０ｘ００２であって、０ｘ００１≦ｒａｎｇｅ＜０ｘ００２となることはない。このため、ＣＡＢＡＣでは、零検出回路２は最大７ビットまで連続する０を検出できれば良く、また８ビットｌｏｗ拡大回路１０は不要である。
【００５０】
（第２の実施形態）
２値算術符号化の過程においてｌｏｗが常に０ｘ２ＦＦ以下に保たれるようにｓｔａｔｅの遷移テーブル（AC_next_state_LPS64、AC_next_state_MPS64）とＬＰＳの発生確率テーブル（rLPS_table_64x4）を設計することも可能である。ｌｏｗが常に０ｘ２ＦＦ以下という条件が満たされるとき、ｌｏｗの拡大処理は第１の実施形態よりも簡単になる。
【００５１】
本実施形態では、ｌｏｗの値は必ず０ｘ２ＦＦ以下となるように、ｓｔａｔｅの遷移テーブルとＬＰＳの発生確率テーブルが設計されており、またｒａｎｇｅのビット幅は９ビットであるものとする。１回目のｌｏｗの拡大処理を以下に示す。
【００５２】
ｌｏｗ＜０ｘ１００のとき、ｌｏｗの上位２ビット＝０ｂ００である。そこで、ｌｏｗの上位２ビットを調べて０ｂ００であれば、ビット出力は０であり、次式を実行する（ステップＳ１３に対応）。
【００５３】
low = low
【００５４】
このとき、ｌｏｗの上位２ビット＝０ｂ００であり、１ビット左論理シフト（ステップＳ１６）後にｌｏｗのＭＳＢ＝０となる。
【００５５】
０ｘ１００≦ｌｏｗ＜０ｘ２００のとき、ｌｏｗの上位２ビット＝０ｂ０１である。そこで、ｌｏｗの上位２ビットを調べて０ｂ０１であれば、ビット出力は未確定であり、次式を実行する（ステップＳ１４に対応）。
【００５６】
low = low - 0x100
【００５７】
このとき、ｌｏｗの上位２ビット＝０ｂ００であり、１ビット左論理シフト（ステップＳ１６）後にｌｏｗのＭＳＢ＝０となる。
【００５８】
０ｘ２００≦ｌｏｗ＜０ｘ３００のとき、ｌｏｗの上位２ビット＝０ｂ１０である。そこで、ｌｏｗの上位２ビットを調べて０ｂ１０であれば、ビット出力は１であり、次式を実行する（ステップＳ１５に対応）。
【００５９】
low = low - 0x200
【００６０】
このとき、ｌｏｗの上位２ビット＝０ｂ００であり、１ビット左論理シフト（ステップＳ１６）後にｌｏｗのＭＳＢ＝０となる。
【００６１】
上記１回目のｌｏｗの拡大処理の結果は必ずｌｏｗ＜０ｘ２００となる。従って、２回目のｌｏｗの拡大処理は以下のようになる。
【００６２】
ｌｏｗ＜０ｘ１００のとき、ｌｏｗの上位から２ビット目、すなわち正規化開始前のｌｏｗの上位から３ビット目を調べて０であれば、ビット出力は０である（ステップＳ１３に対応）。このとき、１ビット左論理シフト（ステップＳ１６）後にｌｏｗのＭＳＢ＝０となる。
【００６３】
０ｘ１００≦ｌｏｗ＜０ｘ２００のとき、ｌｏｗの上位から２ビット目、すなわち正規化開始前のｌｏｗの上位から３ビット目を調べて１であれば、ビット出力は未確定である（ステップＳ１４に対応）。このとき、１ビット左論理シフト（ステップＳ１６）後にｌｏｗのＭＳＢ＝０となる。
【００６４】
このように、２回目のｌｏｗの拡大処理の結果も必ずｌｏｗ＜０ｘ２００となる。同様に、３回目以降のｌｏｗの拡大処理の結果もｌｏｗ＜０ｘ２００となることは明らかである。従って、１回目のｌｏｗの拡大処理を除いて、正規化開始前のｌｏｗの上位から（ｎ＋１）ビット目を調べれば、ｎ回目のｌｏｗの拡大処理の内容を決定することができる。
【００６５】
ｎ回目のｌｏｗの拡大処理を以下に示す。
【００６６】
再正規化が開始される前のｌｏｗの上位から（ｎ＋１）ビット目を調べて０であれば、ビット出力は０である（ステップＳ１３に対応）。
【００６７】
再正規化が開始される前のｌｏｗの上位から（ｎ＋１）ビット目を調べて１であれば、ビット出力は未確定である（ステップＳ１４に対応）。
【００６８】
以上のように、ｌｏｗの拡大処理を第１の実施形態よりも簡単に行うことができる。１ビットｌｏｗ拡大回路３はｌｏｗの上位２ビットを調べることにより処理内容を決定でき、ビット出力は０、１、または未確定の３種類である。１ビットｌｏｗ拡大回路３を除き、ｉビットｌｏｗ拡大回路は、再正規化が開始される前のｌｏｗの（ｉ＋１）ビット目を調べることにより処理内容を決定でき、ビット出力は０または未確定の２種類である。
【００６９】
なお、第１の実施形態と第２の実施形態では、ｒａｎｇｅとｌｏｗのビット幅が９ビットと１０ビットの場合について説明したが、本発明ではｒａｎｇｅとｌｏｗのビット幅は９ビットと１０ビットに限られない。
【００７０】
（第３の実施形態）
H.264/AVC
reference softwareに記述されている正規化の方法では、図３に示すように、ｌｏｗの拡大処理において出力が０または１のいずれにもなる可能性があるときはEbits_to_followがカウントアップされる（ステップＳ１４）。そして、確定した０または１を出力するとき（ステップＳ１３、Ｓ１５）、図４に示すように、この確定した０または１を反転したビットがEbits_to_followに設定されている値の回数だけ出力される（ステップＳ１８、Ｓ１９）。
【００７１】
一方、第１の実施形態または第２の実施形態に示す方法で正規化を行うと、ビット出力として０、１、または未確定の３種類の状態が出力される。本実施形態では、未確定を含むビット出力を０と１のみの確定したビット出力に高速に変換する方法を示す。
【００７２】
未確定という状態をＳで表すと、以下のように変換すれば、図４の処理フローと同じ結果を得ることができる。
【００７３】
出力が０と確定したとき、SSS……SS0を0111……11に変換する。一方、出力が１と確定したときは、SSS……SS1を1000……00に変換する。
【００７４】
本発明では、この変換処理を加算により実現する。本発明における確定したビット出力への変換処理を図６に示す。図６（ａ）は出力が０に確定した場合である。本発明では、Ｓを１とみなし、Ｓの数だけ連続する１のビット列のＬＳＢに０を加算することにより、出力が０と確定したときの変換処理を行う。
【００７５】
図６（ｂ）は出力が１に確定した場合である。出力が１と確定した場合には、Ｓの数だけ連続する１のビット列のＬＳＢに１を加算することにより変換処理を行う。
【００７６】
具体的には、ビット出力が未確定のときビット１を設定し、ビット出力が０または１のときビット０を設定することによってビット系列Ｓを作成する。また、ビット出力が１であるときビット１を設定し、ビット出力が０または未確定のときビット０を設定することによってビット系列Ｃを作成する。すなわち、ビット出力が未確定のとき（Ｓ，Ｃ）＝（１，０）、ビット出力が０のとき（Ｓ，Ｃ）＝（０，０）、ビット出力が１のとき（Ｓ，Ｃ）＝（０，１）を設定する。そして、ビット系列Ｓを１ビット右論理シフトしてビット系列Ｃと加算することにより、一括して確定した出力ビット系列に変換する。
【００７７】
ただし、実際の加算器のビット長は有限であるため、一括して変換できるビット数は加算器のビット長に依存する。８ビットごとに一括して変換する回路を図７に示す。この回路を用いて、次の１６ビットの出力ビット系列を８ビットごとに一括して変換する例を図８に示す。
【００７８】
SSSS S1SS S1SS 0SSS → 1000 0010 0001 1SSS
【００７９】
ビット系列Ｓとビット系列Ｃはそれぞれ以下のようになる。
【００８０】
S = 1111 1011 1011 0111
【００８１】
C = 0000 0100 0100 0000
【００８２】
この場合、８ビット加算器１３，１４を用いる。まず、８ビット加算器１４を用いてビット系列Ｓの上位側７ビットの先頭にビット０を付加した「0111 1101」と、ビット系列Ｃの上位側８ビット「0000
0100」を加算する。次に、その加算結果を８ビット加算器１３に設定する。図８では、ビット系列Ｓの上位側８ビットに加算結果を設定し、ビット系列Ｃの上位側８ビットは全て０としたが、ビット系列Ｓの上位側８ビットは全て０とし、ビット系列Ｃの上位側８ビットに加算結果を設定しても良い。そして、再度８ビット加算器１４を用いてビット系列Ｓの８ビット目から１５ビット目の「1101
1011」と、ビット系列Ｃの下位側８ビット「0100 0000」を加算する。そのとき、キャリが８ビット加算器１４から出力され、８ビット加算器１３のＬＳＢに加算される。これにより、上位側８ビットについて出力が確定する。しかし、下位側８ビットについては最後の３ビットが下位側からのキャリの伝播により反転する可能性があり、まだ確定していない。下位側８ビットについては、その加算結果を８ビット加算器１３に設定し、更にその下位８ビットのビット系列ＳとＣについて８ビット加算器１４で同様の計算を行うことにより確定する。なお、図８のビット系列Ｓは１ビット右シフトされるため、最後の１ビットが余るが、この余った１ビットは、下位のビット系列Ｓの先頭に付加する。
【００８３】
ただし、８ビット加算器１４に入力される８ビット全部のビット出力が未確定である場合が問題となる。ビット系列Ｓの８ビットは全て１、かつ、ビット系列Ｃの８ビットは全て０の場合、下位側からキャリが入力しないとき、８ビット加算器１３へのキャリは発生しない。一方、下位側からキャリが伝播してきたときは、８ビット加算器１３へのキャリが発生する。この問題を解決するために、本発明では、０ｘＦＦ検出回路２０でビット系列Ｓの８ビットが全て１であることを検出し、また、ＬＳＢ０検出回路２１でビット系列Ｃの８ビットの中の最下位ビットが０であることを検出する。そして、ビット系列Ｓの８ビットが全て１、かつ、ビット系列Ｃの８ビットの中の最下位ビットが０という条件が成立した場合、その８ビットをビット系列ＳとＣの両方から除去する。ここで、ビット系列Ｃの８ビットの中の最下位ビットが０という条件が必要となる理由は、ビット系列Ｓは１ビット右論理シフトされているため、ビット系列Ｓの８ビットが全て１であっても、ビット系列Ｃの８ビットの中の最下位ビットは１である可能性があるためである。その後、８ビット加算器１４に入力される下位のビット系列ＳとＣについてビット系列Ｓの８ビット中に少なくても１ビットは０が含まれるか、または、ビット系列Ｃの８ビットの中の最下位ビットが１であるといういずれかの条件が成立したとき、８ビット加算器１４からキャリが出力される場合には０ｘ００／０ｘＦＦ挿入回路１７で出力ビット系列に０ｘ００を挿入し、８ビット加算器１４からキャリが出力されない場合には出力ビット系列に０ｘＦＦを挿入する。
【００８４】
なお、第３の実施形態では、８ビット加算器を２個用いたが、２個の加算器のビット長が同じであれば良く、例えば１６ビット加算器を２個用いても良い。
【００８５】
また、本明細書と特許請求の範囲では、ｒａｎｇｅとｌｏｗを拡大する処理を左論理シフトで行うと記載したが、左論理シフトと等しい結果が得られる演算であれば良く、拡大処理を乗算により実現しても良い。
【産業上の利用可能性】
【００８６】
本発明は、静止画や動画の圧縮や音声の圧縮等データを圧縮する分野で利用価値が高い。
【図面の簡単な説明】
【００８７】
【図１】ＣＡＢＡＣに準拠した算術符号化を行うBiari_encode_symbol処理フローを示す図である。
【図２】ｓｙｍｂｏｌがＬＰＳおよびＭＰＳであるときのｒａｎｇｅとｌｏｗの変化を示した説明図である。
【図３】ＣＡＢＡＣに準拠した算術符号化における再正規化を行うRenormalisation処理フローを示す図である。
【図４】確定した０または１を出力し、同時に未確定の出力を確定した出力に変換するput_one_bit_plus_outstanding(b)処理フローを示す図である。
【図５】本発明による再正規化回路のブロック図である。
【図６】本発明における未確定を含むビット出力を確定したビット出力へ変換する例を示す図である。
【図７】本発明における未確定を含むビット出力系列を８ビットごとに一括して確定したビット出力系列へ変換する回路のブロック図である。
【図８】未確定を含む１６ビットのビット出力系列を８ビットごとに一括して確定したビット出力系列へ変換する例を示す図である。
【符号の説明】
【００８８】
１    ｒａｎｇｅシフト回路
２    零検出回路
３    １ビットｌｏｗ拡大回路
４    ２ビットｌｏｗ拡大回路
５    ３ビットｌｏｗ拡大回路
６    ４ビットｌｏｗ拡大回路
７    ５ビットｌｏｗ拡大回路
８    ６ビットｌｏｗ拡大回路
９    ７ビットｌｏｗ拡大回路
１０    ８ビットｌｏｗ拡大回路
１１    ビット出力集約回路
１２    ｌｏｗ選択回路
１３、１４    ８ビット加算器
１５、１６、１８、１９    ８ビットレジスタ
１７    ０ｘ００／０ｘＦＦ挿入回路
２０    ０ｘＦＦ検出回路
２１    ＬＳＢ０検出回路