(57)【要約】  コンテキストシンボルと、バイパスシンボルとが混在しているシンボル列に関しても、高速に符号化することが可能な算術符号化装置等が提供される。算術符号化装置３０１は、発生確率に基づき符号が算出される基である数値範囲を更新するコンテキストシンボルと、所定の確率にて該数値範囲を更新するバイパスシンボルとが混在しているシンボル列に対して、該コンテキストシンボルに関する該発生確率を更新し、更新した該発生確率に基づき、該シンボル列に関する該数値範囲を更新し、さらに、該所定の確率に基づき、更新された該数値範囲を更新する更新部３０２と、算術符号を算出する手順に従い、該更新手段によって更新された該数値範囲に基づき、該シンボル列に関する算術符号を算出する処理部３０３とを有する。
2017195843.tif 000002
【特許請求の範囲】
【請求項１】
発生確率に基づき符号が算出される基である数値範囲を更新するコンテキストシンボルと、所定の確率にて前記数値範囲を更新するバイパスシンボルとが混在しているシンボル列に対して、前記コンテキストシンボルに関する前記発生確率を更新し、更新した前記発生確率に基づき、前記シンボル列に関する前記数値範囲を更新し、前記所定の確率に基づき、更新された前記数値範囲を、さらに、更新する更新手段と、
算術符号を算出する手順に従い、前記更新手段によって更新された前記数値範囲に基づき、前記シンボル列に関する算術符号を算出する処理手段と
を備える算術符号化装置。
【請求項２】
前記更新手段は、コンテキスト―バイパス処理手段と、バイパス―コンテキスト処理手段とを含み、
前記コンテキスト―バイパス処理手段、及び、前記バイパス―コンテキスト処理手段は、
前記コンテキストシンボルに関する前記発生確率を更新し、更新した前記発生確率に基づき、前記シンボル列に関する前記数値範囲を更新するコンテキスト符号化手段と、
前記所定の確率に基づき、前記シンボル列に関する前記数値範囲を更新するバイパス符号化手段と
を含み、
前記コンテキスト―バイパス処理手段において、前記バイパス符号化手段は、前記コンテキスト符号化手段によって更新された前記数値範囲を更新し、
前記コンテキスト―バイパス処理手段において、前記コンテキスト符号化手段は、前記バイパス符号化手段によって更新された前記数値範囲を更新する
請求項１に記載の算術符号化装置。
【請求項３】
前記更新手段は、さらに、複数コンテキスト処理手段と、複数バイパス処理手段とを含み、
前記複数コンテキスト処理手段は、複数の前記コンテキスト符号化手段によって構成され、
前記複数バイパス処理手段は、複数の前記バイパス符号化手段によって構成され、
前記複数コンテキスト処理手段において、前記コンテキスト符号化手段は、異なる前記コンテキスト符号化手段が更新した前記数値範囲を更新し、
前記複数バイパス処理手段において、前記バイパス符号化手段は、異なる前記バイパス符号化手段が更新した前記数値範囲を更新する
請求項２に記載の算術符号化装置。
【請求項４】
前記コンテキストシンボル、または、前記バイパスシンボルによって構成されている第２シンボル列に対して、前記第２シンボル列を構成しているシンボルの並び順に従い、前記第２シンボル列を処理する処理先として、前記コンテキスト―バイパス処理手段、前記バイパス―コンテキスト処理手段、前記複数コンテキスト処理手段、または、前記複数バイパス処理手段を選択し、選択した前記処理先に、前記第２シンボル列に基づき前記数値範囲を出力する選択手段
をさらに備える請求項３に記載の算術符号化装置。
【請求項５】
前記コンテキスト―バイパス処理手段に含まれている前記コンテキスト符号化手段、及び、前記バイパス符号化手段の総数、前記バイパス―コンテキスト処理手段に含まれている前記コンテキスト符号化手段、及び、前記バイパス符号化手段の総数、前記複数コンテキスト処理手段に含まれている前記コンテキスト符号化手段の総数、及び、前記複数バイパス処理手段に含まれている前記バイパス符号化手段の総数は、同じである
請求項３または請求項４に記載の算術符号化装置。
【請求項６】
前記更新手段は、さらに、第２コンテキスト―バイパス処理手段を含み、
前記第２コンテキスト―バイパス処理手段は、前記コンテキスト符号化手段と、第１バイパス符号化手段と、第２バイパス符号化手段とを含み、
前記第２コンテキスト―バイパス処理手段において、前記第１バイパス符号化手段は、前記コンテキスト符号化手段が更新した前記数値範囲を更新し、前記第２バイパス符号化手段は、前記第１バイパス符号化手段が更新した前記数値範囲を更新する
請求項２乃至請求項５のいずれかに記載の算術符号化装置。
【請求項７】
前記更新手段は、さらに、第２バイパス―コンテキスト処理手段を含み、
前記第２バイパス―コンテキスト処理手段は、前記コンテキスト符号化手段と、第３バイパス符号化手段と、第４バイパス符号化手段とを含み、
前記第２バイパス―コンテキスト処理手段において、前記第４バイパス符号化手段は、前記第３バイパス符号化手段が更新した前記数値範囲を更新し、前記コンテキスト符号化手段は、前記第４バイパス符号化手段が更新した前記数値範囲を更新する
請求項２乃至請求項６のいずれかに記載の算術符号化装置。
【請求項８】
発生確率に基づき符号が算出される基である数値範囲を更新するコンテキストシンボルと、所定の確率にて前記数値範囲を更新するバイパスシンボルとが混在しているシンボル列に対して、前記コンテキストシンボルに関する前記発生確率を更新し、更新した前記発生確率に基づき、前記シンボル列に関する前記数値範囲を更新し、さらに、前記所定の確率に基づき、更新された前記数値範囲を更新し、
算術符号を算出する手順に従い、更新された前記数値範囲に基づき、前記シンボル列に関する算術符号を算出する
算術符号化方法。
【請求項９】
発生確率に基づき符号が算出される基である数値範囲を更新するコンテキストシンボルと、所定の確率にて前記数値範囲を更新するバイパスシンボルとが混在しているシンボル列に対して、前記コンテキストシンボルに関する前記発生確率を更新し、更新した前記発生確率に基づき、前記シンボル列に関する前記数値範囲を更新し、さらに、前記所定の確率に基づき、更新された前記数値範囲を更新する更新回路と、
算術符号を算出する手順に従い、前記更新回路によって更新された前記数値範囲に基づき、前記シンボル列に関する算術符号を算出する処理回路と
を備える算術符号化回路。
【請求項１０】
前記更新回路は、コンテキスト―バイパス処理回路と、バイパス―コンテキスト処理回路とを含み、
前記コンテキスト―バイパス処理回路、及び、前記バイパス―コンテキスト処理回路は、
前記コンテキストシンボルに関する前記発生確率を更新し、更新した前記発生確率に基づき、前記シンボル列に関する前記数値範囲を更新するコンテキスト符号化回路と、
前記所定の確率に基づき、前記シンボル列に関する前記数値範囲を更新するバイパス符号化回路と
を含み、
前記コンテキスト―バイパス処理回路において、前記バイパス符号化回路は、前記コンテキスト符号化回路によって更新された前記数値範囲を更新し、
前記コンテキスト―バイパス処理回路において、前記コンテキスト符号化回路は、前記バイパス符号化回路によって更新された前記数値範囲を更新する
請求項９に記載の算術符号化回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、算術符号に従い、データを符号化する算術符号化装置等に関する。
【背景技術】
【０００２】
非特許文献１には、ＩＴＵ−Ｔによって勧告されたＨ．２６５規格に基づく映像符号化方式であるＨＥＶＣ（Ｈｉｇｈ＿Ｅｆｆｉｃｉｅｎｃｙ＿Ｖｉｄｅｏ＿Ｃｏｄｉｎｇ）が記載されている。ＩＴＵ−Ｔは、Ｉｎｔｅｒｎａｔｉｏｎａｌ＿Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎ＿Ｕｎｉｏｎ＿Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎ＿Ｓｔａｎｄａｒｄｉｚａｔｉｏｎ＿Ｓｅｃｔｏｒの略称を表す。Ｈ．２６５は、動画圧縮規格を表す。【０００３】
ＨＥＶＣにおいて、ディジタル化された映像を構成する各フレームは、符号化ツリーユニット（ＣＴＵ：Ｃｏｄｉｎｇ＿Ｔｒｅｅ＿Ｕｎｉｔ）に分割され、ラスタスキャン順にて各ＣＴＵが符号化される。各ＣＴＵは、４つの符号化ユニット（ＣＵ：Ｃｏｄｉｎｇ＿Ｕｎｉｔ）に分割されたクアッドツリー（四分木）構造を有する。各ＣＵは、予測ユニット（ＰＵ：Ｐｒｅｄｉｃｔｉｏｎ＿Ｕｎｉｔ）と呼ばれる単位に分割される。各ＣＵは、分割されたＰＵごとに、動き補償予測や、画像予測を実行する。また、各ＣＵが、これらの予測を実行した際に生じる予測誤差は、クアッドツリー構造、変換ユニット（ＴＵ：Ｔｒａｎｓｆｏｒｍ＿Ｕｎｉｔ）に分割され、分割された予測誤差が周波数変換される。周波数変換された予測誤差は、ＴＵ単位にて量子化され、その後、算術符号化部によって符号化される。【０００４】
算術符号化部は、以下の手順に従い、符号化を行う。まず、複数信号で入力されたＣＵ、ＰＵ、ＴＵの構成情報、及び、量子化後の予測残差は、２値化部によってシンボル列に変換される。シンボルは、たとえば、０、または、１の値である。量子化後の予測残差がシンボル列（０、または、１を含むシンボル列）に変換される処理は、シンボル列に関するシンタックスごとに定められた変換手法に従って実行される。【０００５】
次に、入力されるシンボル列と、シンタックスごとのシンボル列と、シンタックスごとに定められたコンテキストとを用いて符号化する算術符号化が実行される。あるシンタックスに従い構成されているシンボル列が複数である場合に、該シンボル列に含まれているシンボルによって、異なっているコンテキストが作成される場合もある。ここで、コンテキストは、多く出現するシンボル（Ｍｏｓｔ＿Ｐｒｏｂａｂｌｅ＿Ｓｙｍｂｏｌ、ＭＰＳ）と、該ＭＰＳの発生確率（生起確率）との組からなる。ＨＥＶＣにおいては、発生確率と、発生確率の推移は、６１通りの状態数と、該状態間の状態遷移によって表現されている。コンテキストに依存しているシンボルは、コンテキストシンボルと呼ばれる。以降の本願の記載において、コンテキストシンボルは、コンテキストに依存しているシンボルを表すとする。【０００６】
これに対して、ＨＥＶＣにおいては、コンテキストに依存していない（非依存な）特殊なシンボルが存在する。該特殊なシンボルは、バイパスシンボルと呼ばれる。バイパスシンボルの発生確率は、所定の確率（たとえば、５０％）に固定される。バイパスシンボルに関しては、発生確率が所定の確率に固定されるので、コンテキストを更新する必要がない。この結果、バイパスシンボルに関する符号化処理は、コンテキストシンボルに関する符号化処理よりも演算量が少ない。以降の本願の記載において、バイパスシンボルは、コンテキストに依存していない（非依存な）シンボルを表すとする。【０００７】
算術符号化装置の一例は、非特許文献１、及び、特許文献１に開示されている。【０００８】
非特許文献１に記載された算術符号化装置は、コンテキストシンボルを符号化処理するエンジンが直列に接続された構成を有し、最大４つのコンテキストシンボルを１度の処理にて処理することが可能なコンテキストシンボル処理部を有する。また、算術符号化装置は、あらかじめ、シンボル列を、コンテキストシンボルとバイパスシンボルとに分離し、分離したコンテキストシンボルとバイパスシンボルとを、それぞれ、別の処理手段を用いて符号化処理を実行する。【０００９】
特許文献１は、算術符号を算出する手法に従い、入力画像に対する符号を算出する動画像符号化装置を開示している。該動画像符号化装置は、該入力画像が符号化された符号列から復号された画像内の画素値に適用される処理の種別を２値信号に変換し、変換した２値信号を、バイパスシンボルを符号化する手順に従い符号化する。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】国際公開第２０１３／１８３２３２号
【非特許文献】
【００１１】
【非特許文献１】「Ｕｌｔｒａ−ｈｉｇｈ−ｔｈｒｏｕｇｈｐｕｔ  ＶＬＳＩ＿ａｒｃｈｉｔｅｃｔｕｒｅ＿ｏｆ＿Ｈ．２６５／ＨＥＶＣ＿ＣＡＢＡＣ＿  ｅｎｃｏｄｅｒ＿ｆｏｒ＿ＵＨＤＴＶ＿ａｐｐｌｉｃａｔｉｏｎｓ」、  Ｄａｊｉａｎｇ＿Ｚｈｏｕ、Ｊｉｎｊｉａ＿Ｚｈｏｕ、Ｗｅｉ＿Ｆｅｉ、ａｎｄ  Ｓａｔｏｓｈｉ  Ｇｏｔｏ、  ＩＥＥＥ＿Ｔｒａｎｓａｃｔｉｏｎｓ＿ｏｎ＿ＣｉｒＣＵｉｔｓ＿ａｎ＿Ｓｙｓｔｅｍｓ＿ｆｏｒ＿Ｖｉｄｅｏ＿Ｔｅｃｈｎｏｌｏｇｙ  （ＴＣＳＶＴ）、  Ｖｏｌ．  ２５、  Ｎｏ．３、  ｐｐ．  ４９７−５０７、  Ｍａｒｃｈ  ２０１５．
【発明の概要】
【発明が解決しようとする課題】
【００１２】
しかし、特許文献１に開示された動画像符号化装置、及び、非特許文献１に記載された算術符号化装置は、コンテキストシンボルと、バイパスシンボルとが混在しているシンボル列を高速に処理することができない。この理由について説明する。非特許文献１に記載されたコンテキストシンボル処理部は、コンテキストシンボルが連続しているシンボル列を高速に処理できるものの、該シンボル列とは異なる構成を有するシンボル列を処理することができない。したがって、非特許文献１に記載された算術符号化装置は、コンテキストシンボルと、バイパスシンボルとが混在しているシンボル列を高速に処理することができない。また、特許文献１に開示された動画像符号化装置は、複数のシンボルを含むシンボル列を高速に処理可能な構成を有していない。【００１３】
そこで、本発明の目的の１つは、コンテキストシンボルと、バイパスシンボルとが混在しているシンボル列に関しても、高速に符号化することが可能な算術符号化装置等を提供することである。
【課題を解決するための手段】
【００１４】
本発明の一態様において、算術符号化装置は、
発生確率に基づき符号が算出される基である数値範囲を更新するコンテキストシンボルと、所定の確率にて前記数値範囲を更新するバイパスシンボルとが混在しているシンボル列に対して、前記コンテキストシンボルに関する前記発生確率を更新し、更新した前記発生確率に基づき、前記シンボル列に関する前記数値範囲を更新し、さらに、前記所定の確率に基づき、更新された前記数値範囲を更新する更新手段と、
算術符号を算出する手順に従い、前記更新手段によって更新された前記数値範囲に基づき、前記シンボル列に関する算術符号を算出する処理手段と
を備える。【００１５】
また、本発明の他の見地として、算術符号化方法は、
発生確率に基づき符号が算出される基である数値範囲を更新するコンテキストシンボルと、所定の確率にて前記数値範囲を更新するバイパスシンボルとが混在しているシンボル列に対して、前記コンテキストシンボルに関する前記発生確率を更新し、更新した前記発生確率に基づき、前記シンボル列に関する前記数値範囲を更新し、さらに、前記所定の確率に基づき、更新された前記数値範囲を更新し、
算術符号を算出する手順に従い、更新された前記数値範囲に基づき、前記シンボル列に関する算術符号を算出する。【００１６】
また、本発明の他の見地として、算術符号化回路は、
発生確率に基づき符号が算出される基である数値範囲を更新するコンテキストシンボルと、所定の確率にて前記数値範囲を更新するバイパスシンボルとが混在しているシンボル列に対して、前記コンテキストシンボルに関する前記発生確率を更新し、更新した前記発生確率に基づき、前記シンボル列に関する前記数値範囲を更新し、さらに、前記所定の確率に基づき、更新された前記数値範囲を更新する更新回路と、
算術符号を算出する手順に従い、前記更新回路によって更新された前記数値範囲に基づき、前記シンボル列に関する算術符号を算出する処理回路と
を備える。
【発明の効果】
【００１７】
本発明に係る算術符号化装置等によれば、コンテキストシンボルと、バイパスシンボルと混在しているシンボル列に関しても、高速に符号化することができる。
【図面の簡単な説明】
【００１８】
【図１】本発明の第１の実施形態に係る算術符号化装置が有する構成を示すブロック図である。
【図２】第１の実施形態に係る処理選択部が有する構成を示すブロック図である。
【図３】第１の実施形態に係る複数コンテキスト処理部が有する構成を示すブロック図である。
【図４】第１の実施形態に係るコンテキスト―バイパス処理部が有する構成を示すブロック図である。
【図５】第１の実施形態に係るバイパス―コンテキスト処理部が有する構成を示すブロック図である。
【図６】第１の実施形態に係る複数バイパス処理部が有する構成を示すブロック図である。
【図７】第１の実施形態に係る算術符号化装置における処理の流れを示すフローチャートである。
【図８】本発明の第２の実施形態に係る算術符号化回路が有する構成を示すブロック図である。
【図９】本発明の第２の実施形態に係る第２コンテキスト―バイパス処理回路が有する構成を示すブロック図である。
【図１０】本発明の第２の実施形態に係る第２バイパス―コンテキスト処理回路が有する構成を示すブロック図である。
【図１１】本発明の第２の実施形態に係るバイパス処理回路が有する構成を示すブロック図である。
【図１２】第２の実施形態に係る算術符号化装置における処理の流れを示すフローチャートである。
【図１３】第２の実施形態に係る算術符号化回路における処理を概念的に表す図（１／４）である。
【図１４】第２の実施形態に係る算術符号化回路における処理を概念的に表す図（２／４）である。
【図１５】第２の実施形態に係る算術符号化回路における処理を概念的に表す図（３／４）である。
【図１６】第２の実施形態に係る算術符号化回路における処理を概念的に表す図（４／４）である。
【図１７】本発明の第３の実施形態に係る算術符号化装置が有する構成を示すブロック図である。
【図１８】算術符号化装置を有する計算処理装置が有する構成を示すブロック図である。
【発明を実施するための形態】
【００１９】
次に、本発明を実施する実施形態について図面を参照しながら詳細に説明する。
【００２０】
＜第１の実施形態＞
図１を参照しながら、本発明の第１の実施形態に係る算術符号化装置１００が有する構成について詳細に説明する。図１は、本発明の第１の実施形態に係る算術符号化装置１００が有する構成を示すブロック図である。
【００２１】
第１の実施形態に係る算術符号化装置１００は、シンボル列解析部１０１と、コンテキスト情報記憶部１０２と、区間情報記憶部１０３と、選択部１０４と、複数コンテキスト処理部１０５と、コンテキスト―バイパス処理部１０６とを有する。算術符号化装置１００は、さらに、バイパス―コンテキスト処理部１０７と、複数バイパス処理部１０８と、出力処理部１０９とを有する。
【００２２】
図２乃至図６を参照しながら、選択部１０４と、複数コンテキスト処理部１０５と、コンテキスト―バイパス処理部１０６と、バイパス―コンテキスト処理部１０７と、複数バイパス処理部１０８とが有する構成について説明する。
【００２３】
まず、図２を参照しながら、第１の実施形態に係る選択部１０４が有する構成について詳細に説明する。図２は、第１の実施形態に係る選択部１０４が有する構成を示すブロック図である。
【００２４】
選択部１０４は、コンテキスト情報入力選択部１０４１と、コンテキスト情報出力処理部１０４２と、区間情報入力選択部１０４３と、区間情報出力選択部１０４４と、複数シンボル入力選択部１０４５とを有する。
【００２５】
コンテキスト情報入力選択部１０４１は、コンテキスト情報記憶部１０２に格納されているコンテキスト情報を、後述する処理先情報が表す処理先（ｐｒｏｃｅｓｓｉｎｇ  ｕｎｉｔ）に選択的に出力する。コンテキスト情報は、コンテキストシンボルに関する発生確率を表す。コンテキスト情報出力処理部１０４２は、処理先が出力した処理先情報を選択的に入力し、入力した処理先情報をコンテキスト情報記憶部１０２に格納する。区間情報入力選択部１０４３は、区間情報記憶部１０３に格納されている区間情報を、後述する処理先情報が表す処理先に選択的に出力する。区間情報出力選択部１０４４は、処理先が出力した区間情報（区間情報については、算術符号を算出する手順の説明に際して併せて後述する）を選択的に入力し、入力した処理先情報を区間情報記憶部１０３に格納する。複数シンボル入力選択部１０４５は、解析対象であるシンボル列を、後述する処理先情報が表す処理先に選択的に出力する。
【００２６】
背景技術にて上述したように、コンテキストシンボルは、コンテキストに依存しているシンボルを表す。したがって、背景技術にて上述したように、コンテキストシンボルは、該コンテキストシンボルが出現（発生）する発生確率に基づき、算術符号を算出する処理の対象となるシンボルである。バイパスシンボルは、コンテキストに依存していない（非依存な）シンボルを表す。したがって、背景技術にて上述したように、バイパスシンボルは、所定の確率に基づき、算術符号を算出する処理の対象となるシンボルである。
【００２７】
図３を参照しながら、第１の実施形態に係る複数コンテキスト処理部１０５が有する構成について詳細に説明する。図３は、第１の実施形態に係る複数コンテキスト処理部１０５が有する構成を示すブロック図である。
【００２８】
複数コンテキスト処理部１０５は、コンテキスト符号化部１０５１と、コンテキスト符号化部１０５２とを有する。コンテキスト符号化部１０５１は、コンテキスト情報更新部１０５３と、区間情報更新部１０５５とを有する。コンテキスト符号化部１０５２は、コンテキスト情報更新部１０５４と、区間情報更新部１０５６とを有する。コンテキスト符号化部１０５１と、コンテキスト符号化部１０５２とは、同様の機能を有する。コンテキスト情報更新部１０５３と、コンテキスト情報更新部１０５４とは、同様の機能を有する。区間情報更新部１０５５と、区間情報更新部１０５６とは、同様の機能を有する。複数コンテキスト処理部１０５における処理については、算術符号を算出する手順を説明した後に、再度、図３を参照しながら後述する。
【００２９】
図４を参照しながら、第１の実施形態に係るコンテキスト―バイパス処理部１０６が有する構成について詳細に説明する。図４は、第１の実施形態に係るコンテキスト―バイパス処理部１０６が有する構成を示すブロック図である。
【００３０】
コンテキスト―バイパス処理部１０６は、コンテキスト符号化部１０６１と、バイパス符号化部１０６２とを有する。コンテキスト符号化部１０６１は、コンテキスト情報更新部１０６３と、区間情報更新部１０６４とを有する。バイパス符号化部１０６２は、区間情報更新部１０６５を有する。コンテキスト符号化部１０６１は、図３に示されたコンテキスト符号化部１０５１、または、コンテキスト符号化部１０５２が有する機能と同様の機能を有する。コンテキスト情報更新部１０６３は、図３に示されたコンテキスト情報更新部１０５３、または、コンテキスト情報更新部１０５４が有する機能と同様の機能を有する。区間情報更新部１０６４は、図３に示された区間情報更新部１０５５、または、区間情報更新部１０５６が有する機能と同様の機能を有する。コンテキスト―バイパス処理部１０６における処理については、算術符号を算出する手順を説明した後に、再度、図４を参照しながら後述する。
【００３１】
図５を参照しながら、第１の実施形態に係るバイパス―コンテキスト処理部１０７が有する構成について詳細に説明する。図５は、第１の実施形態に係るバイパス―コンテキスト処理部１０７が有する構成を示すブロック図である。
【００３２】
バイパス―コンテキスト処理部１０７は、バイパス符号化部１０７１と、コンテキスト符号化部１０７２とを有する。バイパス符号化部１０７１は、区間情報更新部１０７３を有する。コンテキスト符号化部１０７２は、コンテキスト情報更新部１０７４と、区間情報更新部１０７５とを有する。バイパス符号化部１０７１は、図４に示されたバイパス符号化部１０６２が有する機能と同様の機能を有する。コンテキスト符号化部１０７２は、図３に示されたコンテキスト符号化部１０５１が有する機能と同様の機能を有する。
【００３３】
バイパス―コンテキスト処理部１０７は、たとえば、入力された区間情報が先にバイパス符号化部１０７１によって更新され、更新された区間情報が、コンテキスト符号化部１０７２に入力されるという点にて、コンテキスト―バイパス処理部１０６（図４）が有する構成と異なっている。バイパス―コンテキスト処理部１０７における処理については、算術符号を算出する手順を説明した後に、再度、図５を参照しながら後述する。
【００３４】
図６を参照しながら、第１の実施形態に係る複数バイパス処理部１０８が有する構成について詳細に説明する。図６は、第１の実施形態に係る複数バイパス処理部１０８が有する構成を示すブロック図である。
【００３５】
複数バイパス処理部１０８は、バイパス符号化部１０８１と、バイパス符号化部１０８２とを有する。バイパス符号化部１０８１は、区間情報更新部１０８３を有する。バイパス符号化部１０８２は、区間情報更新部１０８４を有する。バイパス符号化部１０８１、及び、バイパス符号化部１０８２は、図４に示されたバイパス符号化部１０６２が有する機能と同様の機能を有する。複数バイパス処理部１０８における処理については、算術符号を算出する手順を説明した後に、再度、図６を参照しながら後述する。
【００３６】
次に、図１を参照しながら、算術符号化装置１００において実行される処理について説明する。
【００３７】
算術符号化装置１００において、シンボル列解析部１０１は、バイパスシンボルと、コンテキストシンボルのうち、少なくとも一方を含むシンボル列を解析する対象として、該シンボル列における先頭の２つのシンボルを解析（分別）する。ここで、「解析する」とは、シンボル列におけるシンボルの並び順を分別することを表す。該シンボル列においては、バイパスシンボルと、コンテキストシンボルとが隣接していてもよい。シンボル列解析部１０１は、シンボル列を解析する処理において、該２つのシンボルの並び順を特定し、特定した並び順のシンボル列を処理可能な処理先を特定する。処理先は、図１において、複数コンテキスト処理部１０５、コンテキスト―バイパス処理部１０６、バイパス―コンテキスト処理部１０７、または、複数バイパス処理部１０８のうち、いずれかの処理部である。
【００３８】
より具体的に、算術符号化装置１００において実行される処理を、シンボル列に含まれているシンボルごとに説明する。
【００３９】
解析する対象であるシンボル列における先頭の２つのシンボルがともにコンテキストシンボルである場合に、算術符号化装置１００において、シンボル列解析部１０１は、該２つのシンボルを処理可能な処理先として、複数コンテキスト処理部１０５を特定する。シンボル列における先頭の２つのシンボルがともにバイパスシンボルである場合に、算術符号化装置１００において、シンボル列解析部１０１は、該２つのシンボルを処理可能な処理先として、複数バイパス処理部１０８を特定する。シンボル列における先頭の２つのシンボルが、コンテキストシンボル、及び、バイパスシンボルという順に隣接している場合に、シンボル列解析部１０１は、該２つのシンボルを処理可能な処理先として、コンテキスト―バイパス処理部１０６を特定する。シンボル列における先頭の２つのシンボルが、バイパスシンボル、及び、コンテキストシンボルという順に隣接している場合に、シンボル列解析部１０１は、該２つのシンボルを処理可能な処理先として、バイパス―コンテキスト処理部１０７を特定する。
【００４０】
シンボル列解析部１０１は、該２つのシンボルを処理可能な処理先として特定した処理部を表す処理先情報を作成し、作成した処理先情報と、該２つのシンボルとを、選択部１０４に対して出力する。
【００４１】
選択部１０４は、シンボル列解析部１０１が出力した該２つのシンボルと、処理先情報とを入力する。選択部１０４は、該２つのシンボルにコンテキストシンボルが含まれている場合に、コンテキスト情報記憶部１０２から、該コンテキストシンボルに関する発生確率を表すコンテキスト情報を読み取る。該２つのシンボルがともにコンテキストシンボルである場合に、選択部１０４は、各コンテキストシンボルに関するコンテキスト情報を読み取る。選択部１０４は、区間情報記憶部１０３に格納されているシンボル列に関する算術符号が算出される基である値を含む実数の区間（ｒａｎｇｅ）を表す区間情報を読み取る。
【００４２】
ここで、算術符号を算出する手順、及び、区間情報について簡単に説明する。
【００４３】
算術符号が算出される基である区間（数値区間）は、シンボル列に含まれているシンボルの並び順に応じて、順次更新される。説明の便宜上、シンボルは、２種類（シンボルＢ、及び、シンボルＣ）であるとする。シンボルＢは、本願の各実施形態において、バイパスシンボルを表す。シンボルＣは、本願の各実施形態において、コンテキストシンボルを表す。この場合に、シンボル列は、シンボルＢ、及び、シンボルＣによって構成される。この場合に、シンボル列は、該シンボル列に含まれているシンボルの並び順に応じた実数の区間に対応している。たとえば、シンボル列に関して算術符号を算出する処理が行われる前に、区間情報が表す区間は、０から１までの区間である。区間は、シンボルＣに関して、該シンボルＣの発生確率に基づき更新され、シンボルＢに関して、所定の確率に基づき更新される。区間は、シンボル列を構成しているシンボルの並び順に従い、シンボル列を構成している各シンボルに関して更新される。
【００４４】
説明の便宜上、シンボルＢに関する所定の確率が０．８であり、シンボルＣの発生確率が０．２であり、シンボル列が「ＢＣＣ」であるとする。また、実数Ｘから実数Ｙまでの区間を［Ｘ、Ｙ］と表すとする。
【００４５】
まず、シンボル列「ＢＣＣ」における先頭のシンボルＢに関して、該シンボルＢに関する所定の確率０．８を、区間［０、１］の区間である１（＝１−０）に対して掛け算することによって、区間［０、０．８］が算出される。すなわち、シンボル列「ＢＣＣ」における先頭のシンボルＢは、区間［０、０．８］に対応している。
【００４６】
次に、シンボル列「ＢＣＣ」における２番目のシンボルＣに関して、該シンボルＣの発生確率０．２を、区間［０、０．８］の区間である０．８（＝０．８−０）に対して掛け算することによって０．１６が算出される。この場合に、区間［０、０．８］は、区間［０、０．６４］と、区間［０．６４、０．８］（０．６４＝０．８−０．１６）とに分けられる。区間［０、０．６４］は、シンボル列「ＢＣＣ」における２番目のシンボルがシンボルＢである場合の区間を表している。区間［０．６４、０．８］は、シンボル列「ＢＣＣ」における２番目のシンボルがシンボルＣである場合の区間を表している。したがって、区間［０、０．８］は、シンボル列「ＢＣＣ」における２番目のシンボルＣに応じて、区間［０．６４、０．８］に更新される。
【００４７】
次に、シンボル列「ＢＣＣ」における３番目のシンボルＣに関して、該シンボルＣの発生確率０．２を、区間［０．６４、０．８］の区間である０．１６（＝０．８−０．６４）に対して掛け算することによって０．０３２が算出される。この場合に、区間［０．６４、０．８］は、区間［０．６４、０．７６８］と、区間［０．７６８、０．８］（０．７６８＝０．８−０．０３２）とに分けられる。区間［０．６４、０．７６８］は、シンボル列「ＢＣＣ」における３番目のシンボルがシンボルＢである場合の区間を表している。区間［０．７６８、０．８］は、シンボル列「ＢＣＣ」における３番目のシンボルがシンボルＣである場合の区間を表している。したがって、区間［０．６４、０．８］は、シンボル列「ＢＣＣ」における３番目のシンボルＣに応じて、区間［０．７６８、０．８］に更新される。
【００４８】
算術符号を算出する手順に従えば、たとえば、シンボル列「ＢＣＣ」は、区間［０．７６８、０．８］と対応しており、この区間［０．７６８、０．８］のうち、いずれかの値（たとえば、該区間の下限値）が算術符号として算出される。
【００４９】
図１を参照しながら、算術符号化装置１００における処理について説明する。選択部１０４は、区間情報を、入力した処理先情報が表す処理先に対して出力する。２つのシンボルにコンテキストシンボルが含まれている場合に、選択部１０４は、さらに、各コンテキストシンボルに関するコンテキスト情報を、該処理先に対して出力する。言い換えると、処理先が複数バイパス処理部１０８である場合に、２つのシンボルが、ともに、コンテキストシンボルと異なっているので、選択部１０４は、コンテキスト情報を複数バイパス処理部１０８に対して出力しない。
【００５０】
図３を参照しながら、処理先が複数コンテキスト処理部１０５である場合に実行される処理について詳細に説明する。処理先が複数コンテキスト処理部１０５である場合に、選択部１０４は、複数コンテキスト処理部１０５に対して、２つのシンボル、２つのシンボルに関して１番目のシンボルの発生確率を表すコンテキスト情報、２番目のシンボルの発生確率を表すコンテキスト情報、及び、区間情報を出力する。この場合に、２つのシンボルにおいて、１番目のシンボル、及び、２番目のシンボルは、ともに、コンテキストシンボルである。
【００５１】
複数コンテキスト処理部１０５において、コンテキスト符号化部１０５１は、１番目のシンボルと、該１番目のシンボルの発生確率を表すコンテキスト情報と、区間情報とを入力する。複数コンテキスト処理部１０５において、コンテキスト符号化部１０５２は、２番目のシンボルと、該２番目のシンボルの発生確率を表すコンテキスト情報と、コンテキスト符号化部１０５１によって更新された区間情報とを入力する。
【００５２】
コンテキスト符号化部１０５１において、コンテキスト情報更新部１０５３は、１番目のシンボルと、該１番目のシンボルに関するコンテキスト情報とに基づき、コンテキスト情報が表す発生確率を更新する。より具体的に、コンテキスト情報更新部１０５３は、１番目のシンボルの発生確率の値を増やし、増やした発生確率を表すコンテキスト情報を作成する。すなわち、コンテキスト情報更新部１０５３は、入力したコンテキスト情報を、１番目のシンボルに関して更新する。コンテキスト情報更新部１０５３は、作成したコンテキスト情報を区間情報更新部１０５５に対して出力する。コンテキスト情報更新部１０５３は、更新後のコンテキスト情報を、選択部１０４と、区間情報更新部１０５５とに対して出力する。選択部１０４は、コンテキスト情報更新部１０５３が出力したコンテキスト情報を入力し、入力したコンテキスト情報をコンテキスト情報記憶部１０２に格納する。
【００５３】
区間情報更新部１０５５は、２番目のシンボルと、コンテキスト情報更新部１０５３が出力したコンテキスト情報（この場合に、更新後のコンテキスト情報）と、選択部１０４が出力した区間情報とを入力する。コンテキスト符号化部１０５１において、区間情報更新部１０５５は、入力したコンテキスト情報が表す発生確率を用いて、上述したような算術符号を算出する手順に従い、区間情報を更新する。区間情報更新部１０５５は、更新後の区間情報をコンテキスト符号化部１０５２に対して出力する。
【００５４】
コンテキスト符号化部１０５２は、２番目のシンボルと、該２番目のシンボルの発生確率を表すコンテキスト情報と、区間情報更新部１０５５が出力した区間情報とを入力する。コンテキスト符号化部１０５２は、上述したコンテキスト符号化部１０５１における処理と同様の処理を実行する。この結果、コンテキスト符号化部１０５２において、コンテキスト情報更新部１０５４は、２番目のシンボル（この場合に、コンテキストシンボル）に関するコンテキスト情報を更新する。区間情報更新部１０５６は、コンテキスト情報更新部１０５４によって更新されたコンテキスト情報を用いて、上述したような算術符号を算出する手順に従い、区間情報を更新する。区間情報更新部１０５６は、更新後の区間情報を選択部１０４に対して出力する。
【００５５】
まとめると、複数コンテキスト処理部１０５は、１番目のシンボルに関して更新されたコンテキスト情報、及び、２番目のシンボルに関して更新されたコンテキスト情報を選択部１０４に対して出力する。また、複数コンテキスト処理部１０５は、２つのシンボルに含まれている各コンテキストシンボルに関して、更新されたコンテキスト情報に基づき、区間情報を更新し、更新した区間情報を選択部１０４に対して出力する。選択部１０４は、複数コンテキスト処理部１０５が出力したコンテキスト情報と、区間情報とを入力し、入力したコンテキスト情報をコンテキスト情報記憶部１０２に格納し、さらに、入力した区間情報を区間情報記憶部１０３に格納する。
【００５６】
尚、１番目のシンボルと、２番目のシンボルとは、同じコンテキストシンボルであってもよいし、異なるコンテキストシンボルであってもよい。説明の便宜上、図３には、１番目のシンボルと、２番目のシンボルとが異なるシンボルを処理可能な複数コンテキスト処理部１０５が示されている。しかし、１番目のシンボルと、２番目のシンボルとが同じシンボルである場合に、複数コンテキスト処理部１０５においては、コンテキスト情報更新部１０５３がコンテキスト情報を更新し、さらに、コンテキスト情報更新部１０５４が、コンテキスト情報更新部１０５３によって更新されたコンテキスト情報を、直接、入力する態様であってもよい。または、複数コンテキスト処理部１０５は、１番目のシンボルと、２番目のシンボルとが、同じコンテキストシンボルであっても、異なるコンテキストシンボルであっても処理可能な態様を有していてもよい。この場合に、複数コンテキスト処理部１０５は、図３に示されたブロック図に、コンテキスト情報更新部１０５３と、コンテキスト情報更新部１０５４とを接続する線が追加された構成を有する。
【００５７】
図４を参照しながら、処理先がコンテキスト―バイパス処理部１０６である場合に実行される処理について詳細に説明する。処理先がコンテキスト―バイパス処理部１０６である場合に、選択部１０４は、１番目のシンボル、該１番目のシンボルに関するコンテキスト情報、２番目のシンボル、及び、区間情報をコンテキスト―バイパス処理部１０６に対して出力する。この場合に、１番目のシンボルは、コンテキストシンボルである。また、２番目のシンボルは、バイパスシンボルである。
【００５８】
コンテキスト―バイパス処理部１０６において、コンテキスト符号化部１０６１は、１番目のシンボルと、該１番目のシンボルに関するコンテキスト情報と、区間情報とを入力する。コンテキスト符号化部１０６１は、入力した１番目のシンボルと、１番目のシンボルに関するコンテキスト情報を用いて、図３を参照しながら上述したようなコンテキスト符号化部１０５１にて実行される処理と同様の処理を実行する。この処理によって、コンテキスト符号化部１０６１は、１番目のシンボルに関するコンテキスト情報が更新されたコンテキスト情報と、入力した区間情報が、更新後のコンテキスト情報を用いて更新された区間情報とを作成する。コンテキスト符号化部１０６１は、作成した区間情報を、バイパス符号化部１０６２に対して出力する。
【００５９】
バイパス符号化部１０６２は、コンテキスト符号化部１０６１が出力した区間情報と、選択部１０４が出力した２番目のシンボル（この場合に、バイパスシンボル）とを入力する。コンテキスト―バイパス処理部１０６において、区間情報更新部１０６５は、入力した区間情報を、２番目のシンボルに関して、所定の確率を用いて、上述したような算術符号を算出する手順に従い更新する。区間情報更新部１０６５は、更新後の区間情報を選択部１０４に対して出力する。以降、図３を参照しながら説明した処理と同様の処理が、選択部１０４によって実行される。
【００６０】
尚、バイパス符号化部１０６２における区間情報更新部１０６５は、２番目のシンボル（この場合に、バイパスシンボル）に関するコンテキスト情報を入力しない。これは、区間情報更新部１０６５が、２番目のシンボル（この場合に、バイパスシンボル）に関して、所定の確率に基づき区間情報を更新するからである。
【００６１】
図５を参照しながら、処理先がバイパス―コンテキスト処理部１０７である場合に実行される処理について説明する。処理先がバイパス―コンテキスト処理部１０７である場合に、選択部１０４は、１番目のシンボルと、区間情報とをバイパス符号化部１０７１に対して出力し、２番目のシンボルと、２番目のシンボルのコンテキスト情報とをコンテキスト符号化部１０７２に対して出力する。この場合に、１番目のシンボルは、バイパスシンボルである。２番目のシンボルは、コンテキストシンボルである。
【００６２】
バイパス―コンテキスト処理部１０７において、区間情報更新部１０７３は、選択部１０４が出力した区間情報と、１番目のシンボルとを入力し、図４におけるバイパス符号化部１０６２にて実行される処理と同様の処理を実行することによって、入力した区間情報が表す区間が、１番目のシンボルに関して、所定の確率に基づき更新された区間情報を作成する。区間情報更新部１０７３は、作成した区間情報を区間情報更新部１０７５に対して出力する。
【００６３】
コンテキスト符号化部１０７２は、区間情報更新部１０７３が出力した区間情報と、選択部１０４が出力した２番目のシンボルと、２番目のシンボルに関するコンテキスト情報とを入力する。コンテキスト符号化部１０７２において、区間情報更新部１０７５は、図３における区間情報更新部１０５６にて実行される処理と同様の処理を実行することによって、入力した区間情報が表す区間が、２番目のシンボルに関して更新されたコンテキスト情報に基づき、区間情報を更新する。バイパス―コンテキスト処理部１０７は、作成した区間情報を選択部１０４に対して出力する。すなわち、バイパス―コンテキスト処理部１０７に入力された区間情報は、バイパス符号化部１０７１における区間情報更新部１０７３と、コンテキスト符号化部１０７２における区間情報更新部１０７５とによって更新され、更新後の区間情報がバイパス―コンテキスト処理部１０７から出力される。
【００６４】
図６を参照しながら、処理先が複数バイパス処理部１０８である場合に実行される処理について説明する。処理先が複数バイパス処理部１０８である場合に、複数バイパス処理部１０８は、選択部１０４が出力した１番目のシンボルと、２番目のシンボルと、区間情報とを入力する。この場合に、１番目のシンボルと、２番目のシンボルとは、ともに、バイパスシンボルである。
【００６５】
複数バイパス処理部１０８において、バイパス符号化部１０８１は、１番目のシンボルと、選択部１０４が出力した区間情報とを入力する。
【００６６】
バイパス符号化部１０８１において、区間情報更新部１０８３は、図４を参照しながら説明したような、区間情報更新部１０６５が実行する処理と同様の処理を実行することによって、１番目のシンボルに関して、所定の確率に基づき区間情報を更新する。区間情報更新部１０８３は、更新した区間情報を区間情報更新部１０８４に対して出力する。区間情報更新部１０８４は、区間情報更新部１０８３が出力した区間情報と、選択部１０４が出力した２番目のシンボル（この場合に、バイパスシンボル）とを入力し、図４を参照しながら説明したような、区間情報更新部１０６５が実行する処理と同様の処理を実行することによって、入力した区間情報を２番目のシンボルに関して更新する。区間情報更新部１０８４は、更新した区間情報を選択部１０４に対して出力する。
【００６７】
選択部１０４は、４つの処理部（複数コンテキスト処理部１０５、コンテキスト―バイパス処理部１０６、バイパス―コンテキスト処理部１０７、複数バイパス処理部１０８）のうち、いずれか１つの処理部が出力した区間情報を選択的に入力する。選択部１０４は、入力した区間情報を、区間情報記憶部１０３に格納する。選択部１０４は、いずれか１つの処理部がコンテキスト情報を出力した場合には、該コンテキスト情報を選択的に入力し、入力したコンテキスト情報をコンテキスト情報記憶部１０２に格納する。
【００６８】
出力処理部１０９は、入力したシンボル列に含まれているシンボルに関して、上述したような処理が完了した場合に、上述した算術符号を算出する手順に従い、入力した区間情報に基づき算術符号を作成する。
【００６９】
次に、図７を参照しながら、本発明の第１の実施形態に係る算術符号化装置１００における処理について詳細に説明する。図７は、第１の実施形態に係る算術符号化装置１００における処理の流れを示すフローチャートである。
【００７０】
まず、算術符号化装置１００は、たとえば、外部装置（不図示）が出力したシンボル列を入力する。算術符号化装置１００において、シンボル列解析部１０１は、入力したシンボル列におけるシンボルの並び順を解析する（ステップＡ１）ことによって、シンボル列に含まれているシンボルのうち、連続している２つのシンボルを処理する処理先を表す処理先情報を作成する（ステップＡ２乃至ステップＡ４に示された判定処理）。
【００７１】
より具体的に、シンボル列解析部１０１は、入力したシンボル列のうち、連続している２つのシンボルを読み取り、読み取った２つのシンボルに関して、それぞれ、バイパスシンボルであるのか、または、コンテキストシンボルであるのかを判定する。
【００７２】
２つのシンボルが、ともに、コンテキストシンボルである場合に（ステップＡ２にてＹＥＳ）、シンボル列解析部１０１は、該２つのシンボルを処理する処理先として、複数コンテキスト処理部１０５を選択し、選択した処理先を表す処理先情報を作成する。シンボル列解析部１０１は、作成した処理先情報と、該２つのシンボルとを、選択部１０４に対して出力する。選択部１０４は、コンテキスト情報記憶部１０２から、各シンボルに関するコンテキスト情報を読み取り、さらに、区間情報記憶部１０３に格納されている区間情報（算術符号について上述したように、初期状態においては、たとえば、［０、１］なる数値区間を表す区間情報）を読み取る。
【００７３】
選択部１０４は、２つのシンボルと、各シンボルに関するコンテキスト情報と、区間情報とを、複数コンテキスト処理部１０５に対して出力する（ステップＡ５）。複数コンテキスト処理部１０５は、該２つのシンボルと、２つのシンボルに関するコンテキスト情報と、区間情報とを入力し、入力したコンテキスト情報と、区間情報とに対して、図３を参照しながら上述したような処理を実行することによって、区間情報と、各シンボルに関するコンテキスト情報とを更新する（ステップＡ６）。複数コンテキスト処理部１０５は、更新後のコンテキスト情報と、更新後の区間情報とを選択部１０４に対して出力する。
【００７４】
２つのシンボルのうち、１番目のシンボルがコンテキストシンボルであり、２番目のシンボルがバイパスシンボルである場合に（ステップＡ２にてＮＯ、かつ、ステップＡ３にてＹＥＳ）、シンボル列解析部１０１は、該２つのシンボルを処理する処理先として、コンテキスト―バイパス処理部１０６を選択し、選択した処理先を表す処理先情報を作成する。シンボル列解析部１０１は、作成した処理先情報と、該２つのシンボルとを、選択部１０４に対して出力する。選択部１０４は、コンテキスト情報記憶部１０２から、該２つのシンボルのうちコンテキストシンボルに関するコンテキスト情報を読み取り、さらに、区間情報記憶部１０３に格納されている区間情報を読み取る。
【００７５】
選択部１０４は、該２つのシンボルと、コンテキストシンボルに関するコンテキスト情報と、区間情報とを、コンテキスト―バイパス処理部１０６に対して出力する（ステップＡ７）。コンテキスト―バイパス処理部１０６は、該２つのシンボルと、コンテキストシンボルに関するコンテキスト情報と、区間情報とを入力し、入力したコンテキスト情報と、区間情報とに対して、図４を参照しながら上述したような処理を実行することによって、区間情報と、該コンテキスト情報とを更新する（ステップＡ８）。コンテキスト―バイパス処理部１０６は、更新後のコンテキスト情報と、更新後の区間情報とを選択部１０４に対して出力する。
【００７６】
２つのシンボルのうち、１番目のシンボルがバイパスシンボルであり、２番目のシンボルがコンテキストシンボルである場合に（ステップＡ３にてＮＯ、かつ、ステップＡ４にてＹＥＳ）、シンボル列解析部１０１は、該２つのシンボルを処理する処理先として、バイパス―コンテキスト処理部１０７を選択し、選択した処理先を表す処理先情報を作成する。シンボル列解析部１０１は、作成した処理先情報と、該２つのシンボルとを、選択部１０４に対して出力する。選択部１０４は、コンテキスト情報記憶部１０２から、該２つのシンボルのうちコンテキストシンボルに関するコンテキスト情報を読み取り、さらに、区間情報記憶部１０３に格納されている区間情報を読み取る。
【００７７】
選択部１０４は、該２つのシンボルと、コンテキストシンボルに関するコンテキスト情報と、区間情報とを、バイパス―コンテキスト処理部１０７に対して出力する（ステップＡ９）。バイパス―コンテキスト処理部１０７は、該２つのシンボルと、コンテキストシンボルに関するコンテキスト情報と、区間情報とを入力し、入力したコンテキスト情報と、区間情報とに対して、図５を参照しながら上述したような処理を実行することによって、区間情報と、該コンテキスト情報とを更新する（ステップＡ１０）。バイパス―コンテキスト処理部１０７は、更新後のコンテキスト情報と、更新後の区間情報とを選択部１０４に対して出力する。
【００７８】
２つのシンボルが、ともに、バイパスシンボルである場合に（ステップＡ４にてＮＯ）、シンボル列解析部１０１は、該２つのシンボルを処理する処理先として、複数バイパス処理部１０８を選択し、選択した処理先を表す処理先情報を作成する。シンボル列解析部１０１は、作成した処理先情報と、該２つのシンボルとを、選択部１０４に対して出力する。選択部１０４は、区間情報記憶部１０３に格納されている区間情報を読み取る。
【００７９】
選択部１０４は、該２つのシンボルと、読み取った区間情報とを、複数バイパス処理部１０８に対して出力する（ステップＡ１１）。複数バイパス処理部１０８は、選択部１０４が出力した区間情報を入力し、入力した区間情報に対して、図６を参照しながら上述したような処理を実行することによって、区間情報を更新する（ステップＡ１２）。複数バイパス処理部１０８は、更新後の区間情報を選択部１０４に対して出力する。
【００８０】
選択部１０４は、４つの処理部のうち、いずれか１つの処理部が出力した区間情報を選択的に入力し、入力した区間情報を区間情報記憶部１０３に格納する（ステップＡ１３）。処理先が複数コンテキスト処理部１０５、コンテキスト―バイパス処理部１０６、または、バイパス―コンテキスト処理部１０７である場合に、選択部１０４は、コンテキスト情報を入力し、入力したコンテキスト情報を、コンテキスト情報記憶部１０２に格納する（ステップＡ１３）。
【００８１】
シンボル列解析部１０１は、入力したシンボル列に含まれているすべてのシンボルに関する処理が完了したか否かを判定する（ステップＡ１４）。入力したシンボル列に含まれているすべてのシンボルに関する処理が完了した場合に（ステップＡ１４にてＹＥＳ）、算術符号化装置１００は、該シンボル列に関して区間情報を更新する処理を完了する。入力したシンボル列に、まだ、処理が実行されていないシンボルがある場合に（ステップＡ１４にてＮＯ）、シンボル列解析部１０１は、処理が実施されていないシンボルに関して、ステップＡ１に示された処理を実行する。
【００８２】
入力したシンボル列に含まれているすべてのシンボルに関する処理が完了した場合に（ステップＡ１４にてＹＥＳ）、出力処理部１０９は、区間情報記憶部１０３に格納されている区間情報を読み取る。出力処理部１０９は、上述した算術符号を算出する手順に従い、読み取った区間情報に関して算術符号を作成する。すなわち、この処理によって、出力処理部１０９は、入力したシンボル列に対する算術符号を作成する。
【００８３】
尚、図３乃至図６に例示された処理先は、いずれも、２つのシンボルに関する処理を実行したが、必ずしも、処理する符号が２つでなくともよい。たとえば、３つのシンボルに関する処理を実行する処理部は、符号化部（コンテキスト符号化部、または、バイパス符号化部）を、該３つのシンボルの並び順に応じて接続することによって実現することができる。
【００８４】
処理先は、必ずしも、同数の符号化部（コンテキスト符号化部、または、バイパス符号化部）を有していなくてもよい。説明の便宜上、コンテキスト符号化部における処理時間、バイパス符号化部における処理時間は、一定であるとする。
【００８５】
図３乃至図６に例示されているように、処理先が、いずれも、同数（図３乃至図６に示された例では２つ）の符号化部を有している場合には、入力したシンボル列がいかなる順番でコンテキストシンボルとバイパスシンボルが混在していても、算術符号化装置１００にて処理する処理時間を正確に予測することができる。この理由は、いずれの処理先も、２つのシンボルを処理するので、処理時間がおおよそ一定であるからである。したがって、シンボル列に関する算術符号を所定の時間（期間）内において算出する必要がある場合には、処理先が、該処理時間に応じた個数の符号化部を有する構成によって、算術符号化装置１００を実現することができる。
【００８６】
また、たとえば、奇数個のシンボルからなるシンボル列である場合には、算術符号化装置１００が、該奇数個の符号化部を有する処理先を有していてもよいし、１個の符号化部からなる処理先を有していてもよい。この場合に、シンボル列における最後のシンボルが、１個の符号化部からなる処理先にて処理される。
【００８７】
次に、本発明の第１の実施形態に係る算術符号化装置１００に関する効果について説明する。
【００８８】
本発明の第１の実施形態に係る算術符号化装置１００によれば、コンテキストシンボルと、バイパスシンボルとが混在しているシンボル列に関しても、高速に符号化することができる。この理由は、算術符号化装置１００が、当該シンボル列を高速に処理可能なコンテキスト―バイパス処理部１０６と、バイパス―コンテキスト処理部１０７とを有しているからである。この理由について、詳細に説明する。
【００８９】
第１の実施形態に係る算術符号化装置１００は、さらに、２つのコンテキストシンボルからなるシンボル列を高速に処理可能な複数コンテキスト処理部１０５と、２つのバイパスシンボルからなるシンボル列を高速に処理可能な複数バイパス処理部１０８とを有する。したがって、第１の実施形態に係る算術符号化装置１００によれば、１回の処理によって２つのシンボルを処理することができる。第１の実施形態に係る算術符号化装置１００によれば、非特許文献１等に記載の算術符号化装置が、コンテキストシンボルと、バイパスシンボルとが混在しているシンボル列を逐次的に符号化するのに比べ、シンボル間における処理が低減する。したがって、本発明の第１の実施形態に係る算術符号化装置１００によれば、コンテキストシンボルと、バイパスシンボルとが混在しているシンボル列に関しても、高速に符号化することができる。
【００９０】
＜第２の実施形態＞
次に、上述した第１の実施形態を基本とする本発明の第２の実施形態について説明する。
【００９１】
以降の説明においては、本実施形態に係る特徴的な部分を中心に説明すると共に、上述した第１の実施形態と同様な構成については、同一の参照番号を付すことにより、重複する説明を省略する。
【００９２】
図８を参照しながら、本発明の第２の実施形態に係る算術符号化回路２００が有する構成について詳細に説明する。図８は、本発明の第２の実施形態に係る算術符号化回路２００が有する構成を示すブロック図である。
【００９３】
第２の実施形態に係る算術符号化回路２００は、シンボル列解析回路２０１と、コンテキスト情報記憶回路２０２と、区間情報記憶回路２０３と、選択回路２０４と、コンテキスト処理回路２０５と、第１コンテキスト―バイパス処理回路２０６とを有する。算術符号化回路２００は、さらに、第１バイパス―コンテキスト処理回路２０７と、第２コンテキスト―バイパス処理回路２０８と、第２バイパス―コンテキスト処理回路２０９と、バイパス処理回路２１０と、出力処理回路２１１とを有する。
【００９４】
シンボル列解析回路２０１は、シンボル列解析部１０１（図１）が有する機能と同様の機能を有する。コンテキスト情報記憶回路２０２は、コンテキスト情報記憶部１０２（図１）が有する機能と同様の機能を有する。区間情報記憶回路２０３は、区間情報記憶部１０３（図１）が有する機能と同様の機能を有する。選択回路２０４は、選択部１０４（図１）が有する機能と同様の機能を有する。出力処理回路２１１は、出力処理部１０９（図１）が有する機能と同様の機能を有する。コンテキスト処理回路２０５は、複数コンテキスト処理部１０５（図３）が有する機能と同様の機能を有する。第１コンテキスト―バイパス処理回路２０６は、コンテキスト―バイパス処理部１０６（図４）が有する機能と同様の機能を有する。第１バイパス―コンテキスト処理回路２０７は、バイパス―コンテキスト処理部１０７（図５）が有する機能と同様の機能を有する。
【００９５】
次に、図９を参照しながら、第２コンテキスト―バイパス処理回路２０８が有する構成について説明する。図９は、本発明の第２の実施形態に係る第２コンテキスト―バイパス処理回路２０８が有する構成を示すブロック図である。
【００９６】
第２コンテキスト―バイパス処理回路２０８は、コンテキスト符号化回路２０８１と、バイパス符号化回路２０８２と、バイパス符号化回路２０８３とを有する。コンテキスト符号化回路２０８１は、コンテキスト情報更新回路２０８４と、区間情報更新回路２０８５とを有する。バイパス符号化回路２０８２は、区間情報更新回路２０８６を有する。バイパス符号化回路２０８３は、区間情報更新回路２０８７を有する。
【００９７】
コンテキスト符号化回路２０８１は、コンテキスト符号化部１０５１（図３）が有する機能と同様の機能を有する。コンテキスト情報更新回路２０８４は、コンテキスト情報更新部１０５３（図３）が有する機能と同様の機能を有する。区間情報更新回路２０８５は、区間情報更新部１０５５（図３）が有する機能と同様の機能を有する。バイパス符号化回路２０８２と、バイパス符号化回路２０８３とは、バイパス符号化部１０６２（図４）が有する機能と同様の機能を有する。区間情報更新回路２０８６と、区間情報更新回路２０８７とは、区間情報更新部１０６５（図４）が有する機能と同様の機能を有する。このため、本実施形態においては、これらの構成要素が有する機能に関する詳細な説明を省略する。
【００９８】
シンボル列解析回路２０１が選択した出力先（すなわち、第１の実施形態に示した処理先）が第２コンテキスト―バイパス処理回路２０８である場合に実行される処理について説明する。この場合に、シンボル列解析回路２０１が解析する対象であるシンボル列のうち、１番目のシンボルは、コンテキストシンボルであり、２番目のシンボル、及び、３番目のシンボルは、バイパスシンボルである。
【００９９】
出力先が第２コンテキスト―バイパス処理回路２０８である場合に、選択回路２０４は、１番目のシンボルと、１番目のシンボルに関するコンテキスト情報と、区間情報記憶回路２０３に格納されている区間情報を、コンテキスト符号化回路２０８１に対して出力する。選択回路２０４は、２番目のシンボルを、バイパス符号化回路２０８２に対して出力する。選択回路２０４は、３番目のシンボルを、バイパス符号化回路２０８３に対して出力する。
【０１００】
コンテキスト符号化回路２０８１は、コンテキスト符号化部１０５１に関して、図３を参照しながら上述した処理と同様の処理を実行することによって、１番目のシンボルに関して更新されたコンテキスト情報、及び、該コンテキスト情報に基づき更新された区間情報を作成する。コンテキスト符号化回路２０８１は、作成した区間情報を、バイパス符号化回路２０８２に対して出力する。
【０１０１】
バイパス符号化回路２０８２は、コンテキスト符号化回路２０８１が出力した区間情報、及び、選択回路２０４が出力した２番目のシンボル（この場合に、バイパスシンボル）を入力する。バイパス符号化回路２０８２において、区間情報更新回路２０８６は、上述したような算術符号を算出する手順に従い、入力した区間情報が表す区間が、所定の確率に基づき更新された区間情報を作成し、作成した区間情報をバイパス符号化回路２０８３に対して出力する。
【０１０２】
バイパス符号化回路２０８３は、バイパス符号化回路２０８２が出力した区間情報、及び、選択回路２０４が出力した３番目のシンボル（この場合に、バイパスシンボル）を入力する。バイパス符号化回路２０８３において、区間情報更新回路２０８７は、上述したような算術符号を算出する手順に従い、入力した区間情報が表す区間が、所定の確率に基づき更新された区間情報を作成し、作成した区間情報を選択回路２０４に対して出力する。
【０１０３】
次に、図１０を参照しながら、第２バイパス―コンテキスト処理回路２０９が有する構成について説明する。図１０は、本発明の第２の実施形態に係る第２バイパス―コンテキスト処理回路２０９が有する構成を示すブロック図である。
【０１０４】
第２バイパス―コンテキスト処理回路２０９は、バイパス符号化回路２０９１と、バイパス符号化回路２０９２と、コンテキスト符号化回路２０９３とを有する。バイパス符号化回路２０９１は、区間情報更新回路２０９４を有する。バイパス符号化回路２０９２は、区間情報更新回路２０９５を有する。コンテキスト符号化回路２０９３は、コンテキスト情報更新回路２０９６と、区間情報更新回路２０９７とを有する。
【０１０５】
バイパス符号化回路２０９１と、バイパス符号化回路２０９２とは、バイパス符号化部１０６２（図４）が有する機能と同様の機能を有する。区間情報更新回路２０９４と、区間情報更新回路２０９５とは、区間情報更新部１０６５（図４）が有する機能と同様の機能を有する。コンテキスト符号化回路２０９３は、コンテキスト符号化部１０５１（図３）が有する機能と同様の機能を有する。コンテキスト情報更新回路２０９６は、コンテキスト情報更新部１０５３（図３）が有する機能と同様の機能を有する。区間情報更新回路２０９７は、区間情報更新部１０５５（図３）が有する機能と同様の機能を有する。このため、本実施形態においては、これらの構成要素が有する機能に関する詳細な説明を省略する。
【０１０６】
シンボル列解析回路２０１が選択した出力先が、第２バイパス―コンテキスト処理回路２０９である場合に実行される処理について説明する。この場合に、シンボル列解析回路２０１が解析する対象であるシンボル列のうち、１番目のシンボル、及び、２番目のシンボルは、バイパスシンボルであり、３番目のシンボルは、コンテキストシンボルである。
【０１０７】
出力先が第２バイパス―コンテキスト処理回路２０９である場合に、選択回路２０４は、１番目のシンボル（この場合に、バイパスシンボル）と、区間情報記憶回路２０３に格納されている区間情報を、バイパス符号化回路２０９１に対して出力する。選択回路２０４は、２番目のシンボル（この場合に、バイパスシンボル）を、バイパス符号化回路２０９２に対して出力する。選択回路２０４は、３番目のシンボル（この場合に、コンテキストシンボル）と、３番目のシンボルに関するコンテキスト情報とを、コンテキスト符号化回路２０９３に対して出力する。
【０１０８】
バイパス符号化回路２０９１は、選択回路２０４が出力した区間情報と、１番目のシンボル（この場合に、バイパスシンボル）とを入力する。バイパス符号化回路２０９１において、区間情報更新回路２０９４は、上述したような算術符号を算出する手順に従い、入力した区間情報が表す区間が、所定の確率に基づき更新された区間情報を作成し、作成した区間情報をバイパス符号化回路２０９２に対して出力する。
【０１０９】
バイパス符号化回路２０９２は、バイパス符号化回路２０９１が出力した区間情報と、２番目のシンボル（この場合に、バイパスシンボル）とを入力する。バイパス符号化回路２０９２において、区間情報更新回路２０９５は、上述したような算術符号を算出する手順に従い、入力した区間情報が表す区間が、所定の確率に基づき更新された区間情報を作成し、作成した区間情報をコンテキスト符号化回路２０９３に対して出力する。
【０１１０】
コンテキスト符号化回路２０９３は、選択回路２０４が出力した３番目のシンボル（この場合に、コンテキストシンボル）と、該３番目のシンボルに関するコンテキスト情報と、バイパス符号化回路２０９２が出力した区間情報とを入力する。コンテキスト符号化回路２０９３において、コンテキスト情報更新回路２０９６は、コンテキスト情報更新部１０５３に関して図３を参照しながら上述した処理と同様の処理を実行することによって、３番目のシンボルに関して更新されたコンテキスト情報を作成する。区間情報更新回路２０９７は、区間情報更新部１０５５に関して図３を参照しながら上述した処理と同様の処理を実行することによって、３番目のシンボルに関して更新されたコンテキスト情報に基づき、更新された区間情報を作成し、作成した区間情報を選択回路２０４に対して出力する。
【０１１１】
次に、図１１を参照しながら、バイパス処理回路２１０が有する構成について説明する。図１１は、本発明の第２の実施形態に係るバイパス処理回路２１０が有する構成を示すブロック図である。
【０１１２】
バイパス処理回路２１０は、バイパス符号化回路２１０１と、バイパス符号化回路２１０２と、バイパス符号化回路２１０３と、バイパス符号化回路２１０４とを有する。バイパス符号化回路２１０１は、区間情報更新回路２１０５を有する。バイパス符号化回路２１０２は、区間情報更新回路２１０６を有する。バイパス符号化回路２１０３は、区間情報更新回路２１０７を有する。バイパス符号化回路２１０４は、区間情報更新回路２１０８を有する。
【０１１３】
バイパス符号化回路２１０１、乃至、バイパス符号化回路２１０４は、いずれも、バイパス符号化部１０６２（図４）が有する機能と同様の機能を有する。区間情報更新回路２１０５、乃至、区間情報更新回路２１０８は、区間情報更新部１０６５（図４）が有する機能と同様の機能を有する。このため、本実施形態においては、これらの構成要素が有する機能に関する詳細な説明を省略する。
【０１１４】
シンボル列解析回路２０１が選択した出力先がバイパス処理回路２１０である場合に実行される処理について説明する。この場合に、シンボル列解析回路２０１が解析する対象であるシンボル列は、バイパスシンボルのみによって構成されている。
【０１１５】
出力先がバイパス処理回路２１０である場合に、選択回路２０４は、１番目のシンボルと、区間情報記憶回路２０３に格納されている区間情報とを、バイパス符号化回路２０９１に対して出力する。選択回路２０４は、２番目のシンボルを、バイパス符号化回路２１０２に対して出力する。選択回路２０４は、３番目のシンボルを、バイパス符号化回路２１０３に対して出力する。選択回路２０４は、４番目のシンボルを、バイパス符号化回路２１０４に対して出力する。
【０１１６】
バイパス符号化回路２１０１は、選択回路２０４が出力した区間情報と、１番目のシンボル（この場合に、バイパスシンボル）とを入力する。バイパス符号化回路２１０１において、区間情報更新回路２１０５は、上述したような算術符号を算出する手順に従い、入力した区間情報が表す区間が、所定の確率に基づき更新された区間情報を作成し、作成した区間情報をバイパス符号化回路２１０２に対して出力する。
【０１１７】
バイパス符号化回路２１０２は、バイパス符号化回路２１０１が出力した区間情報と、選択回路２０４が出力した２番目のシンボル（この場合に、バイパスシンボル）とを入力する。バイパス符号化回路２１０２において、区間情報更新回路２１０６は、上述したような算術符号を算出する手順に従い、入力した区間情報が表す区間が、所定の確率に基づき更新された区間情報を作成し、作成した区間情報をバイパス符号化回路２１０３に対して出力する。
【０１１８】
バイパス符号化回路２１０３は、バイパス符号化回路２１０２が出力した区間情報と、選択回路２０４が出力した３番目のシンボル（この場合に、バイパスシンボル）とを入力する。バイパス符号化回路２１０３において、区間情報更新回路２１０７は、上述したような算術符号を算出する手順に従い、入力した区間情報が表す区間が、所定の確率に基づき更新された区間情報を作成し、作成した区間情報をバイパス符号化回路２１０４に対して出力する。
【０１１９】
バイパス符号化回路２１０４は、バイパス符号化回路２１０１が出力した区間情報と、選択回路２０４が出力した４番目のシンボル（この場合に、バイパスシンボル）とを入力する。バイパス符号化回路２１０４において、区間情報更新回路２１０８は、上述したような算術符号を算出する手順に従い、入力した区間情報が表す区間が、所定の確率に基づき更新された区間情報を作成し、作成した区間情報を選択回路２０４に対して出力する。
【０１２０】
上述した例において、バイパス処理回路２１０が処理するシンボル列は、４つのバイパスシンボルによって構成されているが、少なくとも、複数のバイパスシンボルによって構成されていればよい。バイパス処理回路２１０におけるバイパス符号化回路が４つであれば、最大４つのバイパスシンボルに関して、算術符号に関する区間情報を更新することができる。
【０１２１】
次に、図１３乃至図１６を参照しながら、本発明の第２の実施形態に係る算術符号化回路２００における処理について詳細に説明する。図１３乃至図１６は、第２の実施形態に係る算術符号化回路２００における処理を概念的に表す図である。
【０１２２】
図１３乃至図１６においては、説明の便宜上、シンボル列解析回路２０１と、選択回路２０４と、コンテキスト処理回路２０５と、第２コンテキスト―バイパス処理回路２０８と、第２バイパス―コンテキスト処理回路２０９と、バイパス処理回路２１０とを示している。図１３乃至図１６においては、コンテキスト情報記憶回路２０２と、区間情報記憶回路２０３と、選択回路２０４と、第１コンテキスト―バイパス処理回路２０６と、第１バイパス―コンテキスト処理回路２０７とに関する記載を省略している。また、図１３に例示されているように、算術符号化回路２００は、９つのシンボルを含むシンボル列４００（すなわち、「ＢＢＢＢＣＣＣＢＢ」）が入力されるとする。図１３内のシンボル列４００において、シンボルＢは、バイパスシンボルを表し、シンボルＣは、コンテキストシンボルを表す。
【０１２３】
図１３に示されているように、シンボル列解析回路２０１は、解析する対象であるシンボル列（この場合に、シンボル列４００）を解析することによって、シンボル列４００のうち先頭４つのシンボルが、いずれも、バイパスシンボルであることを特定する。シンボル列４００のうち、シンボル列４００のうち先頭４つのシンボルが４つまで繰り返しシンボルであるので、シンボル列解析回路２０１は、出力先がバイパス処理回路２１０であることを表す処理先情報を、選択回路２０４に対して出力する。
【０１２４】
選択回路２０４は、シンボル列解析回路２０１によって出力された、シンボル列４００における先頭４つのシンボルと、該４つのシンボルを出力先がバイパス処理回路２１０であることを表す処理先情報とを入力する。図１３に例示されているように、シンボル列４００における先頭４つのシンボルは、いずれも、バイパスシンボル（この場合に、「ＢＢＢＢ」）である。したがって、図１４に例示されているように、選択回路２０４は、区間情報記憶回路２０３に格納されている区間情報を読み取り、読み取った区間情報と、入力したシンボル列４０２とを、入力した処理先情報に従い、バイパス処理回路２１０に対して出力する。シンボル列４０１は、図１３におけるシンボル列４００のうち、まだ、符号化処理されていないシンボル列（すなわち、シンボル列４０２に含まれているシンボル以外のシンボル）を表す。
【０１２５】
バイパス処理回路２１０は、選択回路２０４が出力したシンボル列４０２と、区間情報とを入力し、図１１を参照しながら説明した処理と同様の処理を実行することによって、区間情報を作成する。
【０１２６】
シンボル列解析回路２０１は、シンボル列４００（図１３）のうち、シンボル列４０１（図１４）に関する符号化処理を行っていないので、シンボル列４０１のうち、先頭４つのシンボル（この場合に、「ＣＣＣＢ」）を入力する。この場合に、シンボル列４０１のうち先頭２つのシンボルが、ともに、コンテキストシンボルであるので、シンボル列解析回路２０１は、出力先としてコンテキスト処理回路２０５を選択することを表す処理先情報を、選択回路２０４に対して出力する。
【０１２７】
選択回路２０４は、シンボル列解析回路２０１によって出力された、シンボル列４０１における先頭２つのシンボルと、該２つのシンボルを出力先がコンテキスト処理回路２０５であることを表す処理先情報とを入力する。図１４に例示されているように、シンボル列４０１における先頭２つのシンボルは、いずれも、コンテキストシンボル（すなわち、「ＣＣ」）である。したがって、選択回路２０４は、コンテキスト情報記憶回路２０２から、該２つのコンテキストシンボルに関するコンテキスト情報を読み取り、さらに、区間情報記憶回路２０３に格納されている区間情報を読み取る。図１５に例示されているように、選択回路２０４は、該２つのシンボル（すなわち、シンボル列４０４）と、読み取った区間情報と、読み取ったコンテキスト情報とを、入力した処理先情報に従い、コンテキスト処理回路２０５に対して出力する。シンボル列４０３は、図１４におけるシンボル列４０１のうち、まだ、符号化処理されていないシンボル列（すなわち、シンボル列４０４に含まれているシンボル以外のシンボル）を表す。
【０１２８】
コンテキスト処理回路２０５は、選択回路２０４が出力したシンボル列４０４と、区間情報と、コンテキスト情報とを入力し、図３を参照しながら説明した処理と同様の処理を実行することによって、区間情報、及び、コンテキスト情報を作成する。
【０１２９】
シンボル列解析回路２０１は、シンボル列４０１（図１４）のうち、シンボル列４０３（図１５）に関する符号化処理を行っていないので、シンボル列４０３を入力する。この場合に、シンボル列４０３におけるシンボルが、先頭から順に、コンテキストシンボル、バイパスシンボル、バイパスシンボルであるので、シンボル列解析回路２０１は、出力先として第２コンテキスト―バイパス処理回路２０８を選択することを表す処理先情報を、選択回路２０４に対して出力する。
【０１３０】
選択回路２０４は、シンボル列解析回路２０１によって出力された、シンボル列４０３と、シンボル列４０３を処理する出力先が第２コンテキスト―バイパス処理回路２０８であることを表す処理先情報とを入力する。シンボル列４０３がコンテキストシンボルを含んでいるので、選択回路２０４は、コンテキスト情報記憶回路２０２から、該コンテキストシンボルに関するコンテキスト情報を読み取り、さらに、区間情報記憶回路２０３に格納されている区間情報を読み取る。図１６に例示されているように、選択回路２０４は、シンボル列４０３と、読み取った区間情報と、読み取ったコンテキスト情報とを、入力した処理先情報に従い、第２コンテキスト―バイパス処理回路２０８に対して出力する。
【０１３１】
第２コンテキスト―バイパス処理回路２０８は、選択回路２０４が出力したシンボル列４０３と、区間情報と、コンテキスト情報とを入力し、図９を参照しながら説明した処理と同様の処理を実行することによって、区間情報、及び、コンテキスト情報を作成する。
【０１３２】
シンボル列４００（図１３に例示）に含まれているすべてのシンボルに関する処理が完了したので、シンボル列解析回路２０１は、シンボル列を解析する処理を完了する。この場合に、区間情報記憶回路２０３に格納されている区間情報は、シンボル列４００（図１３に例示）に関する算術符号を算出する基である区間を表す。出力処理回路２１１は、上述したような算術符号を算出する手順に従い、区間情報記憶回路２０３に格納されている区間情報に関して算術符号（すなわち、シンボル列４００に関する算術符号）を算出する。
【０１３３】
次に、図１２を参照しながら、本発明の第２の実施形態に係る算術符号化回路２００における処理について詳細に説明する。図１２は、第２の実施形態に係る算術符号化回路２００における処理の流れを示すフローチャートである。
【０１３４】
シンボル列解析回路２０１は、解析する対象であるシンボル列（たとえば、図１３におけるシンボル列４００）を入力し、入力したシンボル列を解析する（ステップＢ１）。シンボル列解析回路２０１は、入力したシンボル列に基づき、該シンボル列の先頭に位置している複数のシンボル（説明の便宜上、「先頭シンボル列」と表す）を処理する出力先を表す処理先情報を作成し、該先頭シンボル列と、作成した処理先情報とを選択回路２０４に対して出力する。
【０１３５】
選択回路２０４は、シンボル列解析回路２０１が出力した先頭シンボル列と、処理先情報と入力する。その後、選択回路２０４は、区間情報記憶回路２０３に格納されている区間情報を読み取る。選択回路２０４は、入力した先頭シンボル列がコンテキストシンボルを含んでいる場合に、コンテキスト情報記憶回路２０２から、該コンテキストシンボルに関するコンテキスト情報を読み取る。
【０１３６】
選択回路２０４は、入力した処理先情報に基づき出力先を選択し（ステップＢ２、ステップＢ４、ステップＢ６、ステップＢ８、及び、ステップＢ１０）、入力した先頭シンボル列、及び、該区間情報を出力する。入力した先頭シンボル列がコンテキストシンボルを含んでいる場合に、選択回路２０４は、さらに、該出力先に、該コンテキスト情報を出力する。
【０１３７】
より具体的に、入力した先頭シンボル列が２つのコンテキストシンボルである場合に（ステップＢ２にてＹＥＳ）、選択回路２０４は、コンテキスト処理回路２０５に、先頭シンボル列、該コンテキスト情報、及び、該区間情報を出力する。コンテキスト処理回路２０５は、選択回路２０４が出力した、先頭シンボル列、該コンテキスト情報、及び、該区間情報を入力し、図３を参照しながら説明したような処理を実行する（ステップＢ３）。
【０１３８】
入力した先頭シンボル列において、１番目のシンボルがバイパスシンボルであり、２番目のシンボルがバイパスシンボルであり、３番目のシンボルがコンテキストシンボルである場合に（ステップＢ２にてＮＯ、ステップＢ４にてＹＥＳ）、選択回路２０４は、第２バイパス―コンテキスト処理回路２０９に、先頭シンボル列、該コンテキスト情報、及び、該区間情報を出力する。第２バイパス―コンテキスト処理回路２０９は、選択回路２０４が出力した、先頭シンボル列、該コンテキスト情報、及び、該区間情報を入力し、図１０を参照しながら説明したような処理を実行する（ステップＢ５）。
【０１３９】
入力した先頭シンボル列において、１番目のシンボルがコンテキストシンボルであり、２番目のシンボルがバイパスシンボルであり、３番目のシンボルがバイパスシンボルであった場合に（ステップＢ４にてＮＯ、ステップＢ６にてＹＥＳ）、選択回路２０４は、第２コンテキスト―バイパス処理回路２０８に、先頭シンボル列、該コンテキスト情報、及び、該区間情報を出力する。第２コンテキスト―バイパス処理回路２０８は、選択回路２０４が出力した、先頭シンボル列、該コンテキスト情報、及び、該区間情報を入力し、図９を参照しながら説明したような処理を実行する（ステップＢ７）。
【０１４０】
入力した先頭シンボル列において、１番目のシンボルがコンテキストシンボルであり、２番目のシンボルがバイパスシンボルであった場合に（ステップＢ６にてＮＯ、ステップＢ８にてＹＥＳ）、選択回路２０４は、第１コンテキスト―バイパス処理回路２０６に、先頭シンボル列、該コンテキスト情報、及び、該区間情報を出力する。第１コンテキスト―バイパス処理回路２０６は、選択回路２０４が出力した、先頭シンボル列、該コンテキスト情報、及び、該区間情報を入力し、図４を参照しながら説明したような処理を実行する（ステップＢ９）。
【０１４１】
入力した先頭シンボル列において、１番目のシンボルがバイパスシンボルであり、２番目のシンボルがコンテキストシンボルであった場合に（ステップＢ８にてＮＯ、ステップＢ１０にてＹＥＳ）、選択回路２０４は、第１バイパス―コンテキスト処理回路２０７に、先頭シンボル列、該コンテキスト情報、及び、該区間情報を出力する。第１バイパス―コンテキスト処理回路２０７は、選択回路２０４が出力した、先頭シンボル列、該コンテキスト情報、及び、該区間情報を入力し、図５を参照しながら説明したような処理を実行する（ステップＢ１１）。
【０１４２】
ステップＢ１０にてＮＯである場合に（すなわち、入力した先頭シンボル列において、１番目のシンボル、及び、２番目のシンボルが、ともに、バイパスシンボルである場合に）、選択回路２０４は、バイパス処理回路２１０に、先頭シンボル列、該コンテキスト情報、及び、該区間情報を出力する。バイパス処理回路２１０は、選択回路２０４が出力した先頭シンボル列、該コンテキスト情報、及び、該区間情報を入力し、図１１を参照しながら説明したような処理を実行する（ステップＢ１２）。
【０１４３】
次に、図７におけるステップＡ１４に示された処理と同様に、算術符号化回路２００は、入力したシンボル列に含まれているシンボルに関する処理が完了していなければ（図７におけるステップＡ１４に相当）、ステップＢ１に示した処理を実行する。すなわち、ステップＢ１乃至ステップＢ１２に示した処理は、入力されたシンボル列に含まれているシンボルに関する符号化処理が完了するまで繰り返し実行される。
【０１４４】
たとえば、バイパス符号化回路における処理に要する所要時間が、コンテキスト符号化回路における処理に要する所要時間の半分（または、略半分）である場合という前提において考える。この前提において、算術符号化回路２００に対して、シンボル列に関する算術符号を所定の時間（期間）内において算出する必要がある場合には、第２の実施形態に係る算術符号化回路２００は、所定の時間内において処理を完了するのに、好適な構成を有している。この理由は、選択回路２０４が選択する出力先における処理に要する所要時間のばらつきが、１つのバイパスシンボルを処理するのに要する所要時間の半分以内であるので、算術符号化回路２００における処理時間を見積もることが可能であるからである。
【０１４５】
次に、本発明の第２の実施形態に係る算術符号化回路２００に関する効果について説明する。
【０１４６】
本発明の第２の実施形態に係る算術符号化回路２００によれば、コンテキストシンボルと、バイパスシンボルとが混在しているシンボル列に関しても、高速に符号化することができる。この理由は、算術符号化回路２００が、当該シンボル列を高速に処理可能な第１コンテキスト―バイパス処理回路２０６と、第１バイパス―コンテキスト処理回路２０７とを有しているからである。
【０１４７】
さらに、第２の実施形態に係る算術符号化回路２００によれば、第１の実施形態よりもさらに高速に符号化することができる。この理由は、算術符号化回路２００に含まれる各構成要素が処理を実行することによって、第１の実施形態に係る算術符号化装置１００が処理可能なシンボルの個数以上のシンボルが処理されるからである。
【０１４８】
＜第３の実施形態＞
次に、本発明の第３の実施形態について説明する。
【０１４９】
以降の説明においては、本実施形態に係る特徴的な部分を中心に説明すると共に、上述した本発明の各実施形態と同様な構成については、同一の参照番号を付すことにより、重複する説明を省略する。
【０１５０】
図１７を参照しながら、本発明の第３の実施形態に係る算術符号化装置３０１が有する構成について詳細に説明する。図１７は、本発明の第３の実施形態に係る算術符号化装置３０１が有する構成を示すブロック図である。
【０１５１】
第３の実施形態に係る算術符号化装置３０１は、更新部３０２と、処理部３０３とを有する。
【０１５２】
次に、第３の実施形態に係る算術符号化装置３０１における処理について説明する。
【０１５３】
更新部３０２は、１番目のシンボルは、コンテキストシンボルであり、２番目のシンボルは、バイパスシンボルであるシンボル列を入力する。すなわち、更新部３０２は、コンテキストシンボルと、バイパスシンボルとが混在しているシンボル列を入力する。
【０１５４】
更新部３０２は、符号化処理する対象であるシンボル列に含まれているコンテキストシンボルに関する発生確率を表すコンテキスト情報を入力し、入力したコンテキスト情報を更新する。すなわち、入力したシンボル列には、コンテキストシンボルが含まれているので、更新部３０２は、入力したコンテキスト情報が表す発生確率を増やすことによって、コンテキスト情報を更新する。
【０１５５】
次に、更新部３０２は、更新したコンテキスト情報が表す発生確率に基づき、算術符号に関して上述したような手順に従い、シンボル列に関する算術符号を算出する基である区間情報が表す区間（すなわち、数値範囲）を更新する。この処理によって、更新部３０２は、コンテキストシンボルに関して、算術符号を算出する処理を実行する。
【０１５６】
更新部３０２は、コンテキストシンボルに関して更新された数値範囲を、算術符号に関して上述したような手順に従い、所定の確率に基づき更新する。この処理によって、更新部３０２は、バイパスシンボルに関して、算術符号を算出する処理を実行する。
【０１５７】
更新部３０２は、処理部３０３に対して出力する。
【０１５８】
処理部３０３は、更新部３０２が出力した区間情報を入力し、算術符号に関して上述したような手順に従い、該区間情報に基づく算術符号を算出する。すなわち、処理部３０３が算出する算術符号は、算術符号化装置３０１が入力したシンボル列に関する算術符号である。
【０１５９】
更新部３０２は、たとえば、コンテキスト―バイパス処理部１０６（図１）、または、第１コンテキスト―バイパス処理回路２０６（図８）が有する機能を用いて実現することができる。また、処理部３０３は、たとえば、出力処理部１０９（図１）、または、出力処理回路２１１（図８）が有する機能を用いて実現することができる。すなわち、算術符号化装置３０１は、算術符号化装置１００（図１）、または、算術符号化回路２００（図８）が有する機能を用いて実現することができる。
【０１６０】
次に、第３の実施形態に係る算術符号化装置３０１に関する効果について説明する。
【０１６１】
第３の実施形態に係る算術符号化装置３０１によれば、コンテキストシンボルと、バイパスシンボルとが混在しているシンボル列に関しても、高速に符号化することができる。この理由は、算術符号化装置３０１が、当該シンボル列を高速に処理可能な更新部３０２を有しているからである。すなわち、この理由は、算術符号化装置３０１は、１回の処理によって、コンテキストシンボルと、バイパスシンボルとに関する符号化処理を実行することができるからである。第３の実施形態に係る算術符号化装置３０１によれば、非特許文献１等に記載の算術符号化装置が、コンテキストシンボルと、バイパスシンボルとが混在しているシンボル列を逐次的に符号化するのに比べ、シンボル間における処理が低減する。したがって、本発明の第３の実施形態に係る算術符号化装置３０１によれば、コンテキストシンボルと、バイパスシンボルとが混在しているシンボル列に関しても、高速に符号化することができる。
【０１６２】
図１に示された算術符号化装置１００、図８に示された算術符号化回路２００、または、図１７に示された算術符号化装置３０１は、図１８に示されているような計算処理装置５０１にて上述した算術符号を算出する処理を実行する。図１８は、算術符号化装置５０３を有する計算処理装置５０１が有する構成を示すブロック図である。
【０１６３】
計算処理装置５０１は、中央演算処理装置（ＣＰＵ）５０２と、算術符号化装置５０３とを有する。算術符号化装置５０３は、たとえば、図１に示された算術符号化装置１００、図８に示された算術符号化回路２００、または、図１７に示された算術符号化装置３０１である。
【０１６４】
計算処理装置５０１において、算術符号化装置５０３は、たとえば、動画像データに関して上述したような算術符号を算出する処理を実行する。この場合に、ＣＰＵ５０２は、動画像データに関する符号化処理を算術符号化装置５０３に指示し、該指示に応じて算術符号化装置５０３が算出した算術符号を入力する。ＣＰＵ５０２は、算術符号化装置５０３によって符号化されたデータを、該指示を行ってから所定の時間内に入力することによって、遅延することなく動画像データに関する処理を実行することができる。
【０１６５】
尚、図２乃至図６、及び、図９乃至図１１等の図において、矢印の向きは、一例を示すものであり、各部、または、各回路間の信号の向きを限定するものではない。
【０１６６】
以上、上述した実施形態を模範的な例として本発明を説明した。しかし、本発明は、上述した実施形態には限定されない。すなわち、本発明は、本発明のスコープ内において、当業者が理解し得る様々な態様を適用することができる。
【０１６７】
この出願は、２０１６年５月１３日に出願された日本出願特願２０１６−０９６６９３を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【０１６８】
上述した算術符号化装置は、Ｈ．２６５等の規格に従った算術符号化を用いるデータ通信処理、データ保存処理に用いることができる。また、上述した算術符号化装置は、静止画像、及び、動画像に関する符号化を用いている放送、監視、モバイル網を用いている動画配信、遠隔医療といった用途に適用できる。
【符号の説明】
【０１６９】
１００    算術符号化装置
１０１    シンボル列解析部
１０２    コンテキスト情報記憶部
１０３    区間情報記憶部
１０４    選択部
１０５    複数コンテキスト処理部
１０６    コンテキスト―バイパス処理部
１０７    バイパス―コンテキスト処理部
１０８    複数バイパス処理部
１０９    出力処理部
１０４１    コンテキスト情報入力選択部
１０４２    コンテキスト情報出力処理部
１０４３    区間情報入力選択部
１０４４    区間情報出力選択部
１０４５    複数シンボル入力選択部
１０５１    コンテキスト符号化部
１０５２    コンテキスト符号化部
１０５３    コンテキスト情報更新部
１０５４    コンテキスト情報更新部
１０５５    区間情報更新部
１０５６    区間情報更新部
１０６１    コンテキスト符号化部
１０６２    バイパス符号化部
１０６３    コンテキスト情報更新部
１０６４    区間情報更新部
１０６５    区間情報更新部
１０７１    バイパス符号化部
１０７２    コンテキスト符号化部
１０７３    区間情報更新部
１０７４    コンテキスト情報更新部
１０７５    区間情報更新部
１０８１    バイパス符号化部
１０８２    バイパス符号化部
１０８３    区間情報更新部
１０８４    区間情報更新部
２００    算術符号化回路
２０１    シンボル列解析回路
２０２    コンテキスト情報記憶回路
２０３    区間情報記憶回路
２０４    選択回路
２０５    コンテキスト処理回路
２０６    第１コンテキスト―バイパス処理回路
２０７    第１バイパス―コンテキスト処理回路
２０８    第２コンテキスト―バイパス処理回路
２０９    第２バイパス―コンテキスト処理回路
２１０    バイパス処理回路
２１１    出力処理回路
２０８１    コンテキスト符号化回路
２０８２    バイパス符号化回路
２０８３    バイパス符号化回路
２０８４    コンテキスト情報更新回路
２０８５    区間情報更新回路
２０８６    区間情報更新回路
２０８７    区間情報更新回路
２０９１    バイパス符号化回路
２０９２    バイパス符号化回路
２０９３    コンテキスト符号化回路
２０９４    区間情報更新回路
２０９５    区間情報更新回路
２０９６    コンテキスト情報更新回路
２０９７    区間情報更新回路
２１０１    バイパス符号化回路
２１０２    バイパス符号化回路
２１０３    バイパス符号化回路
２１０４    バイパス符号化回路
２１０５    区間情報更新回路
２１０６    区間情報更新回路
２１０７    区間情報更新回路
２１０８    区間情報更新回路
４００    シンボル列
４０１    シンボル列
４０２    シンボル列
４０３    シンボル列
４０４    シンボル列
３０１    算術符号化装置
３０２    更新部
３０３    処理部
５０１    計算処理装置
５０２    ＣＰＵ
５０３    算術符号化装置
【図１】
2017195843.tif 000003
【図２】
2017195843.tif 000004
【図３】
2017195843.tif 000005
【図４】
2017195843.tif 000006
【図５】
2017195843.tif 000007
【図６】
2017195843.tif 000008
【図７】
2017195843.tif 000009
【図８】
2017195843.tif 000010
【図９】
2017195843.tif 000011
【図１０】
2017195843.tif 000012
【図１１】
2017195843.tif 000013
【図１２】
2017195843.tif 000014
【図１３】
2017195843.tif 000015
【図１４】
2017195843.tif 000016
【図１５】
2017195843.tif 000017
【図１６】
2017195843.tif 000018
【図１７】
2017195843.tif 000019
【図１８】
2017195843.tif 000020
【国際調査報告】
2017195843.tif 000021
2017195843.tif 000022
2017195843.tif 000023
2017195843.tif 000024