(57)【要約】入力データ（Ｄ１，１０）を符号化して対応する符号化データ（Ｅ２，３０）を生成するエンコーダ（２０）であって、符号化データ（Ｅ２，３０）は、該符号化データ（Ｅ２，３０）で表わされるべき１つ又は複数のシンボルの頻度、確率又はレンジを示す情報を含む、エンコーダ（２０）が提供される。このエンコーダ（２０）は、１つ又は複数のシンボルのうち少なくとも１つに対する頻度、確率又はレンジを示す情報が符号化データ（Ｅ２，３０）に含まれるか否かを示す追加情報を、符号化データ（Ｅ２，３０）に含めるように動作可能である。このエンコーダ（２０）はまた、１つ又は複数のシンボルのうち少なくとも１つに対する頻度、確率又はレンジを示す情報が符号化データ（Ｅ２，３０）に含まれるか否かを示す追加情報であって、単一の可用性ビット情報として表わされる、該追加情報を、符号化データ（Ｅ２，３０）に含めるように動作可能である。このエンコーダ（２０）は有益であるように、符号化データ（Ｅ２，３０）に頻度、確率又はレンジを示す情報が含まれることを、単一の可用性ビット値「７」を用いて表わし、該符号化データ（Ｅ２，３０）に該頻度、確率又はレンジを示す情報が含まれていないことを、単一の可用性ビット値「０」を用いて表わすように動作可能である。【選択図】図１
2017511997.tif 000002
【特許請求の範囲】
【請求項１】
入力データ（Ｄ１，１０）を符号化して対応する符号化データ（Ｅ２，３０）を生成するエンコーダ（２０）であって、前記符号化データ（Ｅ２，３０）は、該符号化データ（Ｅ２，３０）で表わされるべき１つ又は複数のシンボルの頻度、確率又はレンジを示す情報を含み、前記エンコーダ（２０）は、前記１つ又は複数のシンボルのうち少なくとも１つに対する頻度、確率又はレンジを示す情報が前記符号化データ（Ｅ２，３０）に含まれるか否かを示す追加情報を、該符号化データ（Ｅ２，３０）に含めるように動作可能である、
エンコーダ（２０）。
【請求項２】
前記１つ又は複数のシンボルのうち少なくとも１つに対する頻度、確率又はレンジを示す情報が前記符号化データ（Ｅ２，３０）に含まれるか否かを示す追加情報であって、単一の可用性ビット情報として表わされる、該追加情報を、該符号化データ（Ｅ２，３０）に含めるように動作可能である、請求項１に記載のエンコーダ（２０）。
【請求項３】
前記符号化データ（Ｅ２，３０）に前記頻度、確率又はレンジを示す情報が含まれることを、単一の可用性ビット値「７」を用いて表わし、該符号化データ（Ｅ２，３０）に該頻度、確率又はレンジを示す情報が含まれていないことを、単一の可用性ビット値「０」を用いて表わすように動作可能である、請求項２に記載のエンコーダ（２０）。
【請求項４】
前記符号化データ（Ｅ２，３０）で表わされるべき１つ又は複数のシンボルの頻度、確率又はレンジを示す情報は、符号化対象データ（Ｄ１，１０）の１つ又は複数の特性の関数として、前記エンコーダ（２０）によって動的に変更される、請求項１から３の何れかに記載のエンコーダ（２０）。
【請求項５】
前記１つ又は複数の特性は、前記データ（Ｄ１，１０）の種類、該データ（Ｄ１，１０）のコンテンツ及び／又は該データ（Ｄ１，１０）の統計情報の少なくとも１つを含む、請求項４に記載のエンコーダ（２０）。
【請求項６】
前記符号化対象データ（Ｄ１，１０）を複数の部分に分割し、該部分のそれぞれに対して別個に対応する追加情報であって、前記１つ又は複数のシンボルのうち少なくとも１つに対する頻度、確率又はレンジを示す情報が前記符号化データ（Ｅ２，３０）に含まれるか否かを示す、該追加情報を生成するように動作可能である、請求項４又は５に記載のエンコーダ（２０）。
【請求項７】
前記エンコーダ（２０）は、前記データ（Ｄ１，１０）において生じる最小値及び最大値を決定するために該データ（Ｄ１，１０）を解析するように動作可能であり、前記最小値及び最大値を表わす情報は、該エンコーダ（２０）によって前記符号化データ（Ｅ２，３０）に含められ、該最小値及び最大値は、レンジ符号化が用いられる場合、可能性のある利用可能なシンボル値の範囲を制限する、請求項１から６の何れかに記載のエンコーダ（２０）。
【請求項８】
可用性信号を用いずに、前記データ（Ｄ１，１０）に存在する先頭シンボル及び／又は最後尾シンボルを前記符号化データに表わすように動作可能である、請求項７に記載のエンコーダ（２０）。
【請求項９】
前記符号化対象データ（Ｄ１，１０）にレンジ符号化を適用して前記符号化データ（Ｅ２，３０）を生成する前に、該データ（Ｄ１，１０）のエントロピーを修正するように動作可能である、請求項１から８の何れかに記載のエンコーダ（２０）。
【請求項１０】
前記エンコーダ（２０）は、前記データ（Ｄ１，１０）を符号化するように動作可能であり、該データ（Ｄ１，１０）は、録音音声信号、遺伝子配列データ、録画ビデオ信号、静止画像、テキストデータ、感震データ、センサ信号データ、アナログ−デジタル変換（ＡＤＣ）データ、生体信号データ、カレンダーデータ、経済データ、数学的データ、二進数データの少なくとも１つに対応する、請求項１から９の何れかに記載のエンコーダ（２０）。
【請求項１１】
エンコーダ（２０）で入力データ（Ｄ１，１０）を符号化して対応する符号化データ（Ｅ２，３０）を生成する方法であって、前記符号化データ（Ｅ２，３０）は、該符号化データ（Ｅ２，３０）で表わされるべき１つ又は複数のシンボルの頻度、確率又はレンジを示す情報を含み、前記方法は：
前記１つ又は複数のシンボルのうち少なくとも１つに対する頻度、確率又はレンジを示す情報が前記符号化データ（Ｅ２，３０）に含まれるか否かを示す追加情報を、該符号化データ（Ｅ２，３０）に含めるために、前記エンコーダ（２０）を使用すること
を含む、方法。
【請求項１２】
前記１つ又は複数のシンボルのうち少なくとも１つに対する頻度、確率又はレンジを示す情報が前記符号化データ（Ｅ２，３０）に含まれるか否かを示す追加情報であって、単一の可用性ビット情報として表わされる、該追加情報を、該符号化データ（Ｅ２，３０）に含めるために、前記エンコーダ（２０）を使用することを更に含む、請求項１１に記載の方法。
【請求項１３】
前記符号化データ（Ｅ２，３０）に前記頻度、確率又はレンジを示す情報が含まれることを、単一の可用性ビット値「７」を用いて表わし、該符号化データ（Ｅ２，３０）に該頻度、確率又はレンジを示す情報が含まれていないことを、単一の可用性ビット値「０」を用いて表わすために、前記エンコーダ（２０）を使用することを更に含む、請求項１２に記載の方法。
【請求項１４】
前記符号化データ（Ｅ１２，３０）で表わされるべき１つ又は複数のシンボルの頻度、確率又はレンジを示す情報を、前記符号化対象データ（Ｄ１，１０）の特質の関数として動的に変更するために、前記エンコーダ（２０）を使用することを含む、請求項１１から１３の何れかに記載の方法。
【請求項１５】
前記符号化対象データ（Ｄ１，１０）を複数の部分に分割し、該部分のそれぞれに対して別個に対応する追加情報であって、前記１つ又は複数のシンボルのうち少なくとも１つに対する頻度、確率又はレンジを示す情報が前記符号化データ（Ｅ２，３０）に含まれるか否かを示す、該追加情報を生成するために、前記エンコーダ（２０）を使用することを含む、請求項１４に記載の方法。
【請求項１６】
前記方法は前記データ（Ｄ１，１０）を符号化することを含み、該データ（Ｄ１，１０）は、録音音声信号、遺伝子配列情報、録画ビデオ信号、静止画像、テキストデータ、感震データ、センサ信号データ、アナログ−デジタル変換（ＡＤＣ）データ、生体信号データ、カレンダーデータ、経済データ、数学的データ、二進数データの少なくとも１つに対応する、請求項１１から１５の何れかに記載の方法。
【請求項１７】
復号データ（Ｄ３，９０）を生成するために、請求項１から１０の何れかに記載のエンコーダ（２０）によって生成された符号化データ（Ｅ２，３０）を復号する、デコーダ（８０）。
【請求項１８】
（ａ）可用性信号を受け取ることと；
（ｂ）前記符号化データ（Ｅ２，３０）で伝送された頻度、確率又はレンジのテーブルを受け取ることと；
（ｃ）前記（ａ）及び（ｂ）から、完全な頻度表、確率表又はレンジ表を構成することと；
（ｄ）前記符号化データ（Ｅ２，３０）を復号して出力データ（Ｄ３，９０）を生成するために、前記完全な頻度表、確率表又はレンジ表を使用すること
を実行するように動作可能であるデータ処理ハードウェアを備える、請求項１７に記載のデコーダ（８０）。
【請求項１９】
対応するトランスコードデータを生成するために、前記復号出力データ（Ｄ３）にトランスコードを実行するように動作可能である、請求項１７又は１８に記載のデコーダ（８０）。
【請求項２０】
デコーダ（８０）で符号化データ（Ｅ２，３０）を復号する方法であって、請求項１１から１６の何れかに記載の方法とは逆の処理を実行することを含む、方法。
【請求項２１】
（ａ）可用性信号を受け取ることと；
（ｂ）前記符号化データ（Ｅ２，３０）で伝送された頻度、確率又はレンジのテーブルを受け取ることと；
（ｃ）前記処理（ａ）及び（ｂ）から、完全な頻度表、確率表又はレンジ表を構成することと；
（ｄ）前記符号化データ（Ｅ２，３０）を復号して出力データ（Ｄ３，９０）を生成するために、前記完全な頻度表、確率表又はレンジ表を使用すること
を含む、請求項２０に記載の方法。
【請求項２２】
対応するトランスコードデータを生成するために、前記復号出力データ（Ｄ３）にトランスコードを実行することを含む、請求項２０又は２１に記載の方法。
【請求項２３】
請求項１から１０の何れかに記載の少なくとも１つのエンコーダ（２０）と、請求項１７から１９の何れかに記載の少なくとも１つのデコーダ（８０）を備える、コーデック（２０，８０，９５）。
【請求項２４】
非一時的コンピュータ可読記憶媒体を含むコンピュータプログラムであって、前記非一時的コンピュータ可読記憶媒体はコンピュータ可読命令を含み、前記コンピュータ可読命令は、請求項１１から１６の何れかに記載の方法を実装するために、請求項１から１０の何れかに記載のエンコーダ（２０）の計算ハードウェアによって実行可能である、コンピュータプログラム。
【請求項２５】
非一時的コンピュータ可読記憶媒体を含むコンピュータプログラムであって、前記非一時的コンピュータ可読記憶媒体はコンピュータ可読命令を含み、前記コンピュータ可読命令は、請求項１９に記載の方法を実装するために、請求項１７に記載のデコーダ（８０）の計算ハードウェアによって実行可能である、コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、入力データ（Ｄ１）を符号化してそれに対応する符号化データ（Ｅ２）を生成する符号化方法に関する。また本開示は、前述の符号化データ（Ｅ２）を復号してそれに対応する復号データ（Ｄ３）、復号データ（Ｄ３）のトランスコード版の何れか又は両方を生成する復号方法に関する。さらにまた、本開示は、前述の方法を実装するように動作可能なエンコーダとデコーダにも関する。こうしたエンコーダとデコーダは一体でコーデックを形成する。さらに加えて、本開示は、非一時的コンピュータ可読記憶媒体を含むコンピュータプログラム製品であって、非一時的コンピュータ可読記憶媒体はコンピュータ可読命令を含み、コンピュータ可読命令は、前述の方法を実行する計算ハードウェアによって実行可能である、コンピュータプログラム製品にも関連する。
【背景】
【０００２】
概要としては、図１に示すように、入力データ（Ｄ１）１０を符号化する既知の符号化方法は、エンコーダ２０に入る入力データ（Ｄ１）１０を符号化してそれに対応する符号化出力データ（Ｅ２）３０を生成するものであって、入力データ（Ｄ１）１０に対する１つ又は複数の変換４０ａ・４０ｂの適用を伴い、それに対応する変換された符号化出力データ５０を生成する。ここで、変換された符号化出力データ５０は、それに関連付けられる符号表データ６０であって、採用される１つ又は複数の変換を規定する符号表データ６０を有する。符号化変換データ５０と符号表データ６０をまとめて符号化出力データ（Ｅ２）３０と呼ぶ。符号化出力データ（Ｅ２）３０は通常、データキャリア、データ通信ネットワークの何れか又は両方を介して１つ又は複数のデコーダ８０に伝送される。デコーダ８０は、符号化出力データ（Ｅ２）３０を復号してそれに対応する復号データ（Ｄ３）９０を生成するように動作可能である。復号データ（Ｄ３）はデータ（Ｄ１）の再生成版であるが、これに限らず、例えば、１つ又は複数のデコーダ８０でトランスコードされたものでもよい。符号化出力データ（Ｅ２）３０は通常、入力データ（Ｄ１）１０に対して圧縮されるのが望ましい。また、符号化出力データ（Ｅ２）３０が実質的に可逆方式で圧縮され、復号データ（Ｄ３）９０が入力データ（Ｄ１）１０と比べて実現可能な程度に正確であることも望まれる。入力データ（Ｄ１）１０に対して符号化出力データ（Ｅ２）３０で実現可能なデータ圧縮は、符号表データ６０が符号化変換データ５０と比べてかなりの大きさである場合、即ち、符号表データ６０が大幅なデータオーバヘッドに相当する場合は非効率になる可能性がある。エンコーダ２０に関する既知の実装では、符号表データ６０には、入力データ（Ｄ１）１０における元のシンボルに相当する、符号化変換データ５０に存在する符号化「シンボル」の出現頻度や出現確率、レンジを示す情報が含まれる。ただし、符号表データ６０はこれに限定されない。符号表データ６０は、使用される変換とそのパラメータに関する情報を含んでもよい。
【０００３】
既知の実装によっては、符号表データ６０に含まれる確率を修正するためにコンテンツ情報を使用することもある。コンテンツ情報の使用は確率の修正方法として非常に効率的であるが、画像における画素値や画像変換が行われた後の画素値の符号化の場合等、特定の種類のデータにしか効率的でない。
【０００４】
レンジコーデックの基本実装は、例えばウィキペディアの「Range encoding」のサイトに記載されている（「Range encoding」−ウィキペディア、フリー百科事典、アクセス日：2013年12月13日、URL：http://en.wikipedia.org/wiki/Range_encoding）。この基本実装では、少なくとも１つの<EOM>（end-of-message、メッセージ終了）シンボルが使用される。算術符号化（URL：http://en.wikipedia.org/wiki/Arithmetic_coding）はレンジ符号化とよく似ているが、１つの符号小数点数[0, 1]と<EOD>（end-of-data、データ終了）シンボルが使用される。またレンジ符号化は、ビデオ符号化、画像符号化のようなデータ圧縮を必要とするアプリケーションに広く用いられており、相異なる可能なシンボルの確率が既知であるときには、大規模なデータセットの符号化に非常に適している。しかし、符号化対象データが、１つ又は複数のデコーダ８０でシンボルの確率が予め既知でないような特性を有する場合、符号化データ（Ｅ２）３０と共にシンボルの確率を送信する必要がある。そうしないと、レンジ符号化の圧縮効率が著しく悪化する。
【０００５】
出現頻度や出現確率、レンジの値の送出には、追加データ、即ち「消費データ」を含める必要があり、エンコーダ２０で実現可能な全体の圧縮効率に影響を及ぼす。送信されるシンボル頻度や確率、レンジの値が正確になる程、レンジ符号化において実現可能な圧縮効率もそれに応じてよくなるが、精緻な頻度、確率、又はレンジの値の送信にはより多くのデータサイズが必要である。つまり、シンボルに対する正確な頻度、確率、又はレンジの値の送信と、符号化データ（Ｅ２）における最大限の圧縮効率の実現には、トレードオフの関係がある。
【０００６】
一方、今では世界中で伝送・保存されるデータ量は急速に増え続けている。伝送帯域とデータ保存はパラメータを制限しているため、効率的なデータ圧縮方法の提供は多大な利益をもたらす。こうして、レンジ符号を用いて達成可能な圧縮効率を高めるデータ圧縮の改良方法の必要性は高く、例えば、圧縮対象データのサイズがそれ程大きくなくても必要とされる。したがって、レンジ符号化及びそれに類する符号化の利用がこれまで現実的でなかったり有益でなかったり、あるいはその両方であったりした場合でも、レンジ符号化を利用可能にする方法の必要性は高い。
【０００７】
先願の欧州特許公開公報第0166607A2号（出願人：King Reginald Alfred）には、特定時間符号化シンボル（particular time encoded symbol、TES）における（音声）データサンプル伝送の圧縮が、リニア方式（固定長コード）の代わりにノンリニア方式（可変長コード）でビットを表わすことによって改善可能であるような方法が記載されている。この方法は先行コードを利用し、要素の出現確率の順序をエンコーダからデコーダへ送出するために、この先行コードが用いられる。つまり、この方法は、実際に確率を送信するのではなく、その順序を要素が続く限り送信する。
【０００８】
先願の米国特許第6650996B1号（出願人：Garmin Ltd.）には、カノニカルハフマン符号化データを復号する復号構造を規定する第１のデータフィールドと、シンボル表を規定する第２のデータフィールドを利用するデータ構造を採用するシステム、装置、及び方法が記載されている。またシンボル表は、低頻度インデクスを持つシンボルを提供するのに適している。
【摘要】
【０００９】
本開示は、データ（Ｄ１）を符号化してそれに対応する符号化データ（Ｅ２）を生成する改良方法であって、例えばレンジ符号化を用いる状況では、符号化データ（Ｅ２）のデータ圧縮を高めることができるような方法を提供しようとするものである。
【００１０】
また本開示は、前述の改良方法を利用する改良型エンコーダを提供しようとするものである。
【００１１】
第１の態様によれば、入力データ（Ｄ１）を符号化してそれに対応する符号化データ（Ｅ２）を生成するエンコーダが提供される。符号化データ（Ｅ２）は、該符号化データ（Ｅ２）で表わされるべき１つ又は複数のシンボルの頻度、確率又はレンジを示す情報を含み、エンコーダは、１つ又は複数のシンボルのうち少なくとも１つに対する頻度、確率又はレンジを示す情報が符号化データ（Ｅ２）に含まれるか否かを示す追加情報を、該符号化データ（Ｅ２）に含めるように動作可能である。
【００１２】
本発明には、頻度や確率、レンジの情報が符号化対象データ（Ｄ１）におけるシンボルの出現の関数として符号化データ（Ｅ２）内に選択的に含められ、それによって、圧縮率等の符号化効率の向上が可能となるという利点がある。こうした利点は、例えば、符号化対象データ（Ｄ１）の量が少ない程より有益になるような仕方で実現される。
【００１３】
前述の「１つ又は複数のシンボルのうち少なくとも１つに対する…含まれるか否か」という箇所については、この後で詳述される。
【００１４】
第１の態様に従うエンコーダには、レンジ符号化の頻度や確率、レンジの値をより効率的に送出できる改良方法であって、そうした効率的送出が、その改良方法を用いて生成された符号化データに関連して実現されるような方法を利用するという利点がある。
【００１５】
また前述の改良方法は、符号化対象シンボルの数が可能なシンボルの数と比べてあまり多くない場合でも、レンジ符号化の利用を可能にする。既知のレンジ符号化技術では、こうしたデータの符号化は、頻度や確率、レンジの値を送出するのに必要なビット数により不可能であるか、実用的でないか、あるいはその両方である。すなわち、既知のレンジ符号化技術を用いてエンコーダからそれに対応するデコーダへ頻度や確率、レンジの情報が送出されるのに関連して、非実用的なデータオーバヘッドが生じることになる。
【００１６】
第１の態様に従う改良方法は更に、１つ又は複数の<EOM>シンボルを用いて使用されてもよく、あるいは<EOM>シンボルを用いなくてもよい。「EOM」は「メッセージ終了」を表わすのに用いられる。以下で記述される全ての例示的実施形態では、１つ又は複数の<EOM>シンボルを用いずに示されているが、こうした１つ又は複数の<EOM>シンボルが全ての例示的実施形態に追加されてもよい。例えば、このシンボルに対して確率値1を用い、その他の確率値から1を引くことで追加されてもよい。こうした解決方法では、確率値が既知であるため、新たな確率値の送出をする必要は無い。<EOM>シンボルの確率は、データシンボルの数に基づいて算出されてもよい。確率が算出されると、確率表に<EOM>シンボルが追加され、確率値1が与えられる。頻度の合計も1だけ増えるので、全シンボル確率にも影響を及ぼす。このため、<EOM>シンボルに対して追加確率値の送出が必要となる。
【００１７】
第１の態様に従う改良方法はあらゆる種類のデータの符号化に利用可能であり、幅広い領域で使用できる可能性を持つ。こうした符号化対象である「あらゆる種類のデータ」には、遺伝子配列データやＤＮＡ配列データ、ＲＮＡ配列データ、録音音声信号、録画ビデオ信号、静止画像、テキストデータ、感震データ、センサ信号データ、アナログ−デジタル変換（ADC）データ、生体信号データ、カレンダーデータ、経済データ、数学的データ、二進数データの１つ又は複数が含まれる、これらに限定されるものではない。本改良方法では、確率を修正する別のやり方として適応確率とレンジを使用し、データを符号化してそれに対応する符号化データを生成することもできる。適応確率は比較的大規模なデータ列に対して有効であり、特に、シンボルの確率が可変方式で変更されるが、データ列の相異なる部分ではその変化が遅い場合に適している。しかし、適応確率はデータ列の規模が小さくなる程適さなくなる。データ列におけるシンボルの正確な確率に一致させるために確率を適応させようとすると、追加の計算リソースと時間が必要になるからである。
【００１８】
第１の態様に従う改良方法はエンコーダで利用可能であり、この改良方法に対応する逆の方法は、対応するデコーダで利用可能である。このエンコーダとデコーダを組み合わせて前述のコーデックを構成することもできる。デコーダでは、例えば、そのデコーダのデータレンダリング装置やデコーダのデータ記憶装置に対応するデータを提供するために、デコーダで復号されたデータを更に再フォーマットするトランスコードが実行されてもよい。本改良方法は、データ列のシンボルのうち存在する可能性のある別のシンボルに対して、レンジ値や確率値、頻度値の送出が必要か否かを表わすビット0及びビット1の情報を用いる。本改良方法は、どのシンボルがそれ自体の送出された確率値、即ちビット1を必要とし、どのシンボルがビット0等を用いる等でエスケープ可能であるかを決定するために、１つ又は複数の確率閾値を利用してもよい。全てのエスケープデータシンボルは、エンコーダとデコーダにおいて確率値1を使用可能でもよい。あるいは、頻度値や確率値、即ちレンジを持たないような全てのデータシンボルは、レンジ符号化方式ではエスケープシンボル、即ちレンジと共に送出されてもよい。加えて、こうしたエスケープシンボルに対する全てのシンボル値は、例えば非圧縮の元の値として送出されてもよい。
【００１９】
次に、以下の概念（ｉ）から（ｉｉｉ）について詳述する：
（ｉ）「符号化シンボルが既知である」又は
（ｉｉ）エンコーダにおいて「１つ又は複数のシンボルのうち少なくとも１つに対する頻度、確率又はレンジを示す情報が符号化データに含まれるか否かを示す追加情報」又は
（ｉｉｉ）デコーダにおいて「符号化データの符号化シンボルのどれが、頻度、確率又はレンジの情報を用いて復号されるか」。
【００２０】
本開示の実施形態では、シンボル自体が常に既知であることが本質的ではなく、どのシンボルが確率に関連付けられるかが本質的である。したがって、本開示の実施形態では、確率がデータ列等のどのシンボルに関連するかが分かればよく、実用的には、実際のシンボルが何であるかという内容に基づいて知る必要はない。つまり、デコーダ等に送出され、少なくとも１つのシンボルに対して利用可能な情報は、確率情報でなくてはならない。ただし実用上、実際のシンボルが何であるかを知る必要はない。シンボル値が実際に分かっている確率が用いられてもよく、この場合、その情報も当然利用される。
【００２１】
さらに別の実施例を次に記述する。出現頻度や確率、レンジのテーブルが送出される場合、その送出で重要なパラメータは、テーブルの最大インデクスと、送出される確率で符号化されるシンボルに関する情報である。テーブルの最大インデクスは、送出されたテーブルで利用可能な、即ち入力データＤ１に存在する相異なるシンボルが何種類あるか、あるいは最大何種類ありうるかを表わしている。例えば、次の例を検討する：
4, 3, 0, 1, 0, 4, 3, 4
この場合、実際の最大インデクスは4（最小インデクスは0）であり、このデータに存在する相異なるシンボルは最大で5種類（最大インデクス−最小インデクス＋１＝4-0+1）ということになる。実際にデータに存在する異なるシンボルは4種類（0, 1, 3, 4）しかないため、テーブルは、可能な相異なるシンボル数4ではなく、最大インデクス、即ち利用可能な相異なるシンボル数としての3を用いて送出可能である。テーブルの最大インデクス値として値「3」が用いられる場合、各テーブルインデクスに対してどのシンボルが用いられるのかという情報を送出するために、他の機構が用いられてもよい。
【００２２】
こうした方法は、本開示の随所で詳述されることになる。シンボルが順番に並んでいる場合、一つの可能な形態は、実際の最大インデクス（4）と可用性ビット（この場合、例えば11011）を送出することである。この種の送出は、テーブルインデクス0がインデクスと呼ばれるシンボル0と等しくなるように対応付けし、そのシンボルの対は（0, 0）になる。同様に、残りのインデクスとシンボルの対は(1, 1)、(2, 3)、(3, 4)である。こうしたインデクス・シンボル対を、別のテーブルインデクスとして用いられるインデクスを直接定義するために使用し、テーブルの最大インデクスである3、又は相異なるインデクス・シンボル対の数である４を送出することもできる。こうした方法を用いることで、符号表は通常順番に並べられ、シンボルのみの送出で済む。こうした方法は、送出されるテーブルの中のシンボルがその出現頻度に基づいて格納される場合、非常に有益である。
【００２３】
例えばこの場合、インデクス・シンボル対は(0, 4), (1, 0), (2, 3), (3, 1) であり、値4, 0, 3, 1のみがこの順序で送出される。状況によっては：
（ａ）こうした使用されるインデクス・シンボル対が定義済みでもよい；
（ｂ）使用されるインデクス・シンボル対のテーブルのインデクスが送出されてもよく、あるいは、インデクス・シンボル対が符号化データと共に送出されてもよい；
（ｃ）また別の場合、デコーダは、既知の場所から使用対象のインデクス・シンボル対を読み出すこともできる；
（ｄ）さらにまた別の場合、デコーダは、符号化データと共に送出された場所から、使用対象のインデクス・シンボル対を読み出すこともできる。
【００２４】
前述の第１の態様に従う改良方法を用いてエンコーダで符号化されるデータ中におけるシンボル対の出現頻度は、通常互いに異なっており、それらの関連するデータのエントロピーも相異なる。このため、符号化して符号化データ（Ｅ２）を生成するとき、データを小分けにする、即ち複数部分に分割するのが有益である。相異なる部分に対してそれぞれ異なる符号表が使用されることも有益である。本改良方法により、例えば、一つの大規模なデータチャンクをより効率的に小さな部分、即ち小規模データチャンクに分割することができ、それによって、符号表や頻度表の送出が最適化される。この符号化対象データ（Ｄ１）の分割は、その符号化対象データが分割されるとき、そのデータのエントロピーに関しては著しく有益であり、符号化されないデータ（Ｄ１）を圧縮する場合と比べて、符号化データ（Ｅ２）を圧縮する場合の方が圧縮率を向上させることができる。
【００２５】
第１の態様に従って、エンコーダは、１つ又は複数のシンボルのうち少なくとも１つに対する頻度、確率又はレンジを示す情報が符号化データ（Ｅ２）に含まれるか否かを示す追加情報であって、単一の可用性ビット情報として表わされる、該追加情報を、符号化データ（Ｅ２）に含めるように動作可能でもよい。エンコーダはまた、符号化データ（Ｅ２）に頻度、確率又はレンジを示す情報が含まれることを、単一の可用性ビット値「1」を用いて表わし、該符号化データ（Ｅ２）に該頻度、確率又はレンジを示す情報が含まれていないことを、単一の可用性ビット値「０」を用いて表わすように動作可能でもよい。こうした可用性ビットの値がこれとは逆で用いられてもよい。さらに、こうした可用性情報が利用可能なインデクスの数として送出され、実在する情報を指し示すこともできる。こうしたインデクスがそれ自体のままで送出されてもよく、デルタ符号化を用いて送出されてもよい。可用性情報の送出に必要なデータ量を削減する種々の符号化方法が用いられてもよい。選択された符号化方法が利用可能なインデクスの数を含んでもよく、符号化方法が送出対象インデクスの数を必要としてもよい。あるいは、符号表が送出される場合、符号化方法が、全シンボルに対する可用性ビットの値の送出を必要としてもよい。
【００２６】
エンコーダでは、符号化データ（Ｅ２）において表わされるべき１つ又は複数のシンボルの頻度や確率、レンジを示す情報は、符号化対象データ（Ｄ１）の特質、即ち特性の関数として、エンコーダによって動的に変えられてもよい。こうした特性は、データ（Ｄ１）の構造、データ（Ｄ１）のサイズ、データ（Ｄ１）に存在する値の範囲、データ（Ｄ１）に存在する要素の大きさ、データ（Ｄ１）に関連するメタデータの１つ又は複数に関連してもよい。またこうした特性は、例えばデータ（Ｄ１）の種類、データ（Ｄ１）の内容、データ（Ｄ１）の統計の何れか又は全てを表わしてもよい。またエンコーダは、符号化対象データ（Ｄ１）を複数の部分に分割し、該部分のそれぞれに対して別個に対応する追加情報であって、１つ又は複数のシンボルのうち少なくとも１つに対する頻度、確率又はレンジを示す情報が符号化データ（Ｅ２）に含まれるか否かを示す、該追加情報を生成するように動作可能でもよい。
【００２７】
エンコーダは、遺伝子配列情報、ＤＮＡ配列情報、ＲＮＡ配列情報、録音音声信号、録画ビデオ信号、静止画像、テキストデータ、感震データ、センサ信号データ、アナログ−デジタル変換（ADC）データ、生体信号データ、カレンダーデータ、経済データ、数学的データ、二進数データの少なくとも１つに対応するデータを符号化するように動作可能でもよいが、これらに限定されるものではない。
【００２８】
第２の態様によれば、エンコーダで入力データ（Ｄ１）を符号化してそれに対応する符号化データ（Ｅ２）を生成する方法が提供される。符号化データ（Ｅ２）は、該符号化データ（Ｅ２）で表わされるべき１つ又は複数のシンボルの頻度、確率又はレンジを示す情報を含み、本方法は：
（ａ）１つ又は複数のシンボルのうち少なくとも１つに対する頻度、確率又はレンジを示す情報が前記符号化データ（Ｅ２）に含まれるか否かを示す追加情報を、該符号化データ（Ｅ２）に含めるために、このエンコーダを使用することを含む。
【００２９】
本方法は更に、
（ｂ）１つ又は複数のシンボルのうち少なくとも１つに対する頻度、確率又はレンジを示す情報が符号化データ（Ｅ２）に含まれるか否かを示す追加情報であって、単一の可用性ビット情報として表わされる、該追加情報を、該符号化データ（Ｅ２）に含めるために、このエンコーダを使用することを含んでもよい。
【００３０】
本方法はまた更に、
（ｃ）符号化データ（Ｅ２）に前記頻度、確率又はレンジを示す情報が含まれることを、単一の可用性ビット値「1」を用いて表わし、該符号化データ（Ｅ２）に該頻度、確率又はレンジを示す情報が含まれていないことを、単一の可用性ビット値「０」を用いて表わすために、このエンコーダを使用することを含んでもよい。こうした含む／含まないを表わす値「0」と「1」は、これとは逆で使用されてもよい。
【００３１】
本方法は、符号化データ（Ｅ２）で表わされるべき１つ又は複数のシンボルの頻度、確率又はレンジを示す情報を、前記符号化対象データ（Ｄ１）の１つ又は複数の特性の関数として動的に変更するために、このエンコーダを使用することを含んでもよい。ここで、技術用語としての「特質」や「特性」の定義は、前述の内容を参照して行われるものとする。
【００３２】
本方法は、符号化対象データ（Ｄ１）を複数の部分に分割し、該部分のそれぞれに対して別個に対応する追加情報であって、前記１つ又は複数のシンボルのうち少なくとも１つに対する頻度、確率又はレンジを示す情報が前記符号化データ（Ｅ２）に含まれるか否かを示す、該追加情報を生成するために、このエンコーダを使用することを含んでもよい。
【００３３】
本方法は、遺伝子配列情報、録音音声信号、録画ビデオ信号、静止画像、テキストデータ、感震データの少なくとも１つに対応するデータ（Ｄ１）の符号化を含むが、これらに限定されるものではない。遺伝子配列データは電気遊泳装置で生物学的サンプルから得られるため、相当大きなデータ量になることが多く、核塩基類、アミノ酸類の何れか又は両方を規定するデータでは、通常1テラバイトのオーダーに達する。こうしたデータを伝送し処理することは、現在においては相当大きな技術的挑戦であることを示している。
【００３４】
第３の態様によれば、第１の態様に従うエンコーダが生成した符号化データ（E2）を復号するデコーダが提供される。
【００３５】
第４の態様によれば、デコーダで符号化データ（Ｅ２）を復号する方法が提供され、この方法は、第２の態様に従う方法と逆の処理を実行することを含む。
【００３６】
本方法は：
（ａ）可用性信号を受け取ることと；
（ｂ）符号化データ（Ｅ２）で伝送された頻度、確率又はレンジのテーブルを受け取ることと；
（ｃ）前記処理（ａ）及び（ｂ）から、完全な頻度表、確率表又はレンジ表を構成することと；
（ｄ）符号化データ（Ｅ２）を復号して出力データ（Ｄ３）を生成するために、完全な頻度表、確率表又はレンジ表を使用すること
を含む。
【００３７】
本方法では、可用性信号は、可用性を示すビットを少なくとも1ビット含んでもよい。
【００３８】
本方法では、可用性信号は、可用性を示す符号化方法を少なくとも１つ含んでもよい。
【００３９】
本方法では、可用性信号は、可用性を示すインデクス及び／又はインデクス数を少なくとも１つ含んでもよい。
【００４０】
第５の態様によれば、第１の態様に従う少なくとも１つのエンコーダと、第３の態様に従う少なくとも１つのデコーダを備えるコーデックが提供される。
【００４１】
第６の態様によれば、非一時的コンピュータ可読記憶媒体を含むコンピュータプログラム製品であって、非一時的コンピュータ可読記憶媒体はコンピュータ可読命令を含み、コンピュータ可読命令は、第２の態様に従う方法を実装するために、第１の態様に従うエンコーダの計算ハードウェアによって実行可能である、コンピュータプログラム製品が提供される。
【００４２】
第７の態様によれば、非一時的コンピュータ可読記憶媒体を含むコンピュータプログラム製品であって、非一時的コンピュータ可読記憶媒体はコンピュータ可読命令を含み、コンピュータ可読命令は、第４の態様に従う方法を実装するために、第３の態様に従うデコーダの計算ハードウェアによって実行可能である、コンピュータプログラム製品が提供される。
【００４３】
本発明の構成は、添付の特許請求の範囲に定義される本発明の範囲を逸脱しない限りにおいて、様々に組合せ可能であることを理解されたい。
【図面の簡単な説明】
【００４４】
以下、本開示の実施形態を、一例として次の図面を参照しながら説明する。
【図１】入力データ（Ｄ１）を符号化してそれに対応する符号化出力データ（Ｅ２）を生成するように動作可能であるエンコーダと、符号化データ（Ｅ２）を復号してそれに対応する復号データ（Ｄ３）を生成するように動作可能である、エンコーダに対応するデコーダの図である。
【図２】本開示に従うデータ符号化方法のフローチャートである。
【図３】本開示に従うデータ復号方法のフローチャートである。  添付図面において下線の引かれた番号は、その番号が位置するアイテムやその番号が隣接するアイテムを表わすために使用される。番号に下線が無く矢印を伴って書かれている場合、その番号は矢印が示す汎用アイテムを特定するのに使用される。
【本開示の実施形態の説明】
【００４５】
一般に、データ（Ｄ１）を符号化するレンジ符号化を採用する場合、この符号化対象データ（Ｄ１）におけるシンボルの出現確率を知らなくてはならない。そうでなければ、それに応じて、こうしたレンジ符号化で実現可能な圧縮効率が著しく劣化することになる。各シンボルの確率は、符号化中における「レンジ」を規定し、この確率が高い程、レンジも広くなる。シンボルが符号化されるとき、その符号化されるシンボルの確率に従って、それに対応するレンジが更新される。レンジが十分狭くなると、レンジコーダは例えば１バイトを放出してレンジを広げる。こうして、共通のシンボルが多い程、そのレンジはゆっくりと狭められ、１バイトの放出前により多くにシンボルを符号化することができる。
【００４６】
エンコーダにレンジ符号化を実装する場合、頻度表インデクスや確率表インデクス、レンジ表インデクスは、デコーダで既に分かっている、即ち既知でない限り、それに対応するエンコーダが所定の精度で生成した符号化データ（Ｅ２）で送信される。エンコーダは、符号化対象データ（Ｄ１）の相異なる部分に対して、頻度値、確率値、レンジ値の何れかを動的に切り換えるように動作可能である。その際、それぞれに対応して頻度表インデクス、確率表インデクス、レンジ表インデクスの何れかが用いられる。例えば、レンジコーデックで8ビットデータが符号化される場合、可能なシンボル数は28、即ち256になる。１個の頻度値、確率値又はレンジ値の送信に対して8ビット、即ち1バイトが使用された場合、全ての頻度値、確率値又はレンジ値の送信には256バイトが必要になる。場合によっては、レンジエンコーダから獲得される圧縮データの量が256バイトより少ない可能性もある。したがって、頻度値や確率値、レンジ値の送出にはより少ないビット数の使用で済むことも明らかである。換言すれば、エンコーダからデコーダへの頻度値、確率値又はレンジ値の送出は、実際の符号化対象データの量よりも多い可能性のあるデータオーバヘッドをもたらすことになり、これが圧縮率の性能劣化に対応する。
【００４７】
本開示に従う、データ（Ｄ１）を符号化する方法は、シンボルの出現頻度値や確率値、レンジ値に加えて、シンボル毎に可用性を示す信号、例えば1ビットの可用性ビットも送信される点で、既知の方法とは異なる。この可用性ビットの値は有用であるように、符号化データ（Ｅ２）に現れ、十分高い確率を有する全てのシンボルに対して「1」、符号化データ（Ｅ２）に現れない全てのシンボルに対して「0」、符号化データ（Ｅ２）に現れるが、比較的低い確率を有する全てのシンボルに対しても「0」を示す。
【００４８】
本開示に従う、データ（Ｄ１）を符号化する方法では、シンボルが十分低い確率を有するかを、例えばシンボルの確率を閾値と比較することで調べる。複数の閾値が用いられてもよい。シンボルを符号化するとき、符号化データ（Ｅ２）に存在しないシンボル、又は閾値よりも低い確率を有するシンボルの確率は「0」（そのシンボルに対してエスケープコードが用いられ、レンジは保存されない）又は「1」（即ち、最小可能レンジと共に送出される低確率シンボル）である。すなわち、「0」や「1」は、符号化データ（Ｅ２）３０を生成するためにエンコーダ２０に提供される入力データ（Ｄ１）１０を符号化するのに用いられるレンジ全体の大きさとは無関係である。これは、エンコーダ２０と１つ又は複数のデコーダ８０がそれぞれ改良方法（Ｔ）とその逆変換（T-1）を用いる場合に関係する。出現頻度や確率、レンジと可用性信号（例えば、本実施例では可用性ビット）を送信するのに必要な（ビット単位の）符号化データ量Aは、符号化データ（Ｅ２）に存在する又はそこで利用可能な、十分高い確率を有するシンボル数NSと、出現頻度や確率、レンジの値の各々に使用されるビット数NBとの積に、全シンボルに対する1ビットの可用性ビットOSを加えたもので、次式で表わされる：
［式１］
A = NS * NB + OS
【００４９】
本開示に従う改良発明の次の実施例は、入力データ（Ｄ１）１０としてのデータ値セットを符号化して、それに対応する符号化データ（Ｅ２）３０を生成するエンコーダ２０に適用される。この実施例では、コード化データ列（Ｄ１）に150のデータ値が含まれ、これらが20種のシンボル（＝値）0から19を含むことができる。ただし、これら可能な20種のデータ値のうち8種で、最小値2、最大値19であるものが実際に現行データ列に現れるとする。この最小値と最大値は、例えば、英国特許出願第1303661.1号、出願日2013年3月1日、出願人Gurulogic Microsystems Oyに開示されているODelta符号化法での記載から導出されてもよい。「ODelta」符号化は、特に効率的なデータ符号化を提供する、オフセットとラップアラウンド計算を用いるデルタ符号化法に関連する。これにより、可用性ビットの送出に必要なビット数の削減を可能にする。また、ODelta符号化のようなエントロピーを修正する方法が、レンジ符号化の使用前に利用される場合では、可能性のある利用可能なシンボル値のデータ範囲を削減することもできる。最小値と最大値の利用に関連する最大の利点は、エントロピーを修正する全ての方法とレンジ符号化が同一情報を使用し、その情報がエンコーダからそれに対応するデコーダへ一度だけ送出される場合に発揮される。次の表１は、例として、シンボルの頻度と確率を示す。確率は、頻度をデータ値の総数で割って算出される。
【表１】
2017511997.tif 000003
【００５０】
表１には、出現頻度が非常に低いシンボルも幾つか存在する。確率の送出に7ビットが使用される場合、各確率を表わすのに同じビット数が用いられると、全ての確率を表わすには20*7 = 140ビットが必要になる。データ列、即ち符号化データ（Ｅ２）３０におけるシンボルの有無が、例えばシンボル毎に1ビットの可用性ビットを送信して表わされる場合、全ての確率を表わすには、まだ8*7 + 20*1 = 76ビットが必要である。
【００５１】
本開示に従う改良発明を実装する、既に説明した最初の実施形態は、こうした別々の可用性ビットを用いることで送出される確率の数を20から8に減らす既知の解決方法とは異なる。この後で記述する、本開示に従う別の実施形態に関しては、閾値を用いて、所定の確率がデコーダ８０へ送信されるか否かを確実に決定させるようにすることも有益である。例えば、この閾値が7ビット確率で0.018に設定されてもよい。閾値の変更により、符号化データ（Ｅ２）３０での確率の表現及び１つ又は複数のデコーダ８０への送出に必要なビット数も変わる。表１に記載されたデータに対する閾値として0.10が選択される場合、2つのシンボルしか残らないので、符号化データ（Ｅ２）３０で確率を表わすのに必要なビット数は2*x + 20*1ビットである。ここで、xは、確率の表現に用いられるビット数を表わす。
【００５２】
本開示に従う改良発明を実装するときに用いる最適な閾値は、エンコーダ２０から１つ又は複数のデコーダ８０へ送信されるべき符号化データ（Ｅ２）３０の量と、その符号化データ（Ｅ２）３０で表わされるシンボルの出現頻度に応じて探索される。前述した１つ又は複数の閾値の決定方法は、この後詳細に解明される。例として、
Tを閾値、
Bを、確率を表現するのに用いられるビット数、
とする。例えば前述の表１では、確率は6ビット又は7ビットで表現可能である。閾値は、有益であるよう所定の推奨制限内にあるが、式２で定まるような下限閾値 TLOWよりも下回らない。
2017511997.tif 000004
【００５３】
表１の右４列には、１つ又は複数のデコーダ８０に送信される実際の確率が示されている。「7ビット確率」には、8種又は20種の全てのデータ値に7ビットが使用される場合に、可用性信号を伴って、又は伴わずに送信される確率が示されている。ここで、可用性信号は、データ列におけるシンボルの有無を表わす信号のことである。「7ビット確率（エスケープ有り）」は、本開示に従う改良発明の第１の実施形態を利用して送信される確率に対応し、「7（又は6）ビット確率（修正済）」は、本開示に従う改良発明の第２の実施形態を利用して送信される確率に対応する。
【００５４】
表１の右３列における括弧内の確率は、値0の可用性ビットを用いて表わされため、実際には１つ又は複数のデコーダ８０には送信されない。この実施例では、１つ又は複数のデコーダ８０に送信される確率は、既知の符号化方法で送信される確率に近い値であるため、本開示に従う改良発明を使用しても実際のレンジ符号化の効率を有意に上げることはない。しかし、出現頻度や確率、レンジの値の送信に必要なビット数を削減することによって、全圧縮効率を著しく向上させることができる。また表から自明であるが、既知の方式やエスケープ有りの場合で送信される確率の合計は128であるのに対し、第２の実施形態に従う改良方法では送信される確率の合計は114又は49となっている。これは、可用性ビットが0であるデータ値のそれぞれに対して確率値「1」を受け取ることによる結果である。ここで、データ値は14又は15あり、12種のデータ値はデータ列に存在せず、閾値未満の確率を有する値が2又は3種存在する。
【００５５】
この7ビットと閾値を使用する実施例では、シンボル4と9は、可用性ビットが0で、データ列に存在しない全12種のシンボルと共に表わされる。データ列に存在しないこうしたシンボルに対しては、当初、エスケープと呼ばれる範囲が受け取られていなかったため、確率を持たないシンボル4や9も送出する機構が必須になる。これは、以下で記述する２つの別個の実施形態を用いて効率的な実行が可能となる。
【００５６】
第１の実施形態は表１の「（エスケープ有り）」で示され、別々のエスケープシンボルとそれに関連する範囲（レンジ）が生成される。シンボルは、その範囲を持たない場合にはエスケープ（レンジ）を用いて送出される。またシンボル値も、そのデータ列で送出される。この実施例ではシンボル値は0から19までであるため、シンボル値は5ビットで送出可能である。利用可能なシンボルの数を可能な全シンボルの数で割った割合が高い、即ち0.25を超える場合、シンボル値に対応する可用性ビット0の位置と共にシンボル値を送出することによって、ビット数を若干少なくとしてシンボル値を送出することができ、有益である。例えばこの実施例の場合、シンボル値4はビット列で可用性ビット0が3に対応し、シンボル値9は可用性ビット0が7に対応して、ビット列全体は「00100001000011100001」となる。したがって、ビット列で利用可能な可用性ビット0の数は14しかなく、これを表わすのに、即ち符号化データ（Ｅ２）で表現するのに必要なビット数は4で済む。別のシンボル値データ列の送出が禁止されてもよい。すなわち、レンジ符号化の確率が通常の確率から、全シンボルの確率を等確率に変えてもよい。あるいは、実際のデータ値を送出するエスケープ（レンジ）シンボルの送出の後に可用性ビットが0である全シンボルの確率が等確率にされ、実際のシンボル値が送出されるときに確率が元の通常の確率値に戻されてもよい。
【００５７】
第２の実施形態では、全ての可用性ビット0のシンボルが確率「1」に割り当てられ、確率の全範囲から除いた残りの範囲は、可用性ビット1のシンボル用に保存される。こうした解決方法は表１の「（修正済）」で示され、以下で記述する。前述の7ビットの実施例では12 + 2個のエスケープシンボルがあり、128種の利用可能な値のうち14の値が割り当てられる。残りの114種の値は、可用性ビット1に割り当てられる6種のシンボルに使用される。表１の最後の列には、レンジ確率に6ビットを用いる同様の実施例が示されており、この実施例の閾値として0.4が選択されている。前述のように、ビット列にあるこうした可用性ビット0がエスケープシンボルとして解釈可能である場合、これら全てに対して、表１の括弧内に示されるように確率「1」が割り当てられる。
【００５８】
確率値の送出に必要なビット数は次の通りである。統合（エスケープ有り）解決方法では、7*7 + 20*1 = 69ビットが使用される。しかし、この実施例では最適な解決方法ではない。確率表の送出では、本開示の第１の実施形態と比べて7（= 76 - 69）ビットしか削減できず、追加されたエスケープシンボル値の送出に3*4 = 12ビットを使うからである。したがって、１つ又は複数のエスケープシンボルの確率が元のシンボルよりも高い場合は、データサイズの増加を相殺するには十分でない。この場合、他のシンボルの確率は同じであり、こうした他のシンボルの送出は有益ではない。
【００５９】
この改良方法は別のやり方でも有用である。例えば、多数のシンボルがエスケープされる場合、その確率はあまり高くはない。場合によっては、エスケープシンボル用として元のシンボル用のビット数よりも少ないビット数を利用することもできる。統合エスケープコードを用いるときは如何なる場合でも最小確率が送出されるからである。修正確率を用いる第２の実施形態では、6*7 + 20*1 = 62ビット（7ビット確率）又は5*6 + 20*1 = 50ビット（6ビット確率）が使われる。確率の送出は、符号化データ（Ｅ２）３０に現れる最大頻度のシンボルの確率を示す情報を知ること又はその情報の送出によって、更に最適化されてもよい。
【００６０】
検討中のこうした実施例において、確率の最大値が64未満で、32未満の確率が6ビット（及び5ビット）で送出されてもよい場合、全確率表の送出に必要なビット数は6*6 + 20*1 = 56ビット（7ビットの場合）、及び5*5 + 20*1 = 45ビット（6ビットの場合）で済む。また、この20個の1から成る可用性ビット列の送出は圧縮されてもよい。可用性ビットの圧縮に加え、頻度表や確率値の圧縮によって本開示に従う実施形態を実装することもできる。こうした圧縮が１つ又は複数の圧縮方法を用いて実装されてもよい。このような場合としては特に、可能性のある利用可能なシンボルが多数あり、可用性ビット0の確率と可用性ビット1の確率が様々存在する場合、即ち、多数の0又は多数の1が在る場合や、こうしたビットが符号化データ（Ｅ２）３０におけるビット列の様々な箇所に在る場合が挙げられる。利用可能なシンボルの範囲が、例えば最小値と最大値の何れか又は両方を送出することで別々に制限される場合、最初と最後のシンボルの何れか又は両方は、ビット列で利用可能であるために分かっていればよく、可用性信号を用いて伝送される必要はない。例えば、こうしたシンボルに対する可用性ビットの送出は不要であり、最小値+1から最大値-1までの範囲に対して可用性ビット等の可用性信号を送出すればよい。この表１の実施例では、シンボルの有無が表現されている第１の改良方法と比べて削減されるビット数は、31 (76 - 45)ビットである。既知の方法と比べた場合は、95 (140 - 45)ビットが削減される。この削減効果はシンボルの正確な確率値の数が少なくても失われないため、こうした改良方法は、この実施例におけるデータ送出としては明らかに有利な方法である。
【００６１】
また、正確な確率値の数が少なくても、符号化データ（Ｅ２）３０で確率情報が送出されてもよい。あるいは、高い閾値を用いて、符号化データ（Ｅ２）３０での確率表の送出においてデータサイズを更に削減してもよい。確率表送出での削減は通常、エントロピー符号化においては情報の欠損に繋がる。こうした欠損は、本開示の実施形態を実装するときに最も可能性の高いテーブル送出方法を選択する場合に考慮されなくてはならない。
【００６２】
本開示の改良方法はまた、場合により元データに用いられ、データサイズを削減するようにしてもよい。例えば、データベースやデータキャリア等に保存する場合に用いられてもよい。前述の実施例では当然ながら、元データには150のシンボルと8種の相異なる値が含まれており、元の情報である150*5 = 750ビットは、元データに関する可用性ビット情報を直接用いることによって、150*3 + 20*1 = 470ビットで送出することができる。テーブル送出を伴うレンジ符号化とエントロピー符号化は、元データよりもデータサイズを小さくすることができる。当然ながら、レンジ符号化の前、データのエントロピーを修正する別の方法を用いることもできる。同様に、その逆の動作がレンジ復号の後に行われる必要もある。エントロピーを修正するこうした方法には、例えばデルタ符号化やODelta符号化、即ち、英国特許出願第1303661.1号、出願日2013年3月1日、出願人Gurulogic Microsystems Oyに開示された方法（以下、参照により本願に組み込まれる。ここで、ODelta符号化はデルタ符号化、オフセット計算、ラップアラウンド計算の組合せを採用する）、entropy modifier（EM）、即ち、英国特許出願第1303658.7号、出願日2013年3月1日、出願人Gurulogic Microsystems Oyに開示された方法（以下、参照により本願に組み込まれる）、ランレングス符号化（RLE）、分割ランレングス符号化（SRLE）、即ち、英国特許出願第1303660.3号、出願日2013年3月1日、出願人Gurulogic Microsystems Oyに開示された方法（以下、参照により本願に組み込まれる）が含まれる。
【００６３】
前述のように、本開示に従う改良方法には、レンジ符号化を実装する場合、１つ又は複数の<EOM>シンボルを利用せず、符号化対象データの量（＝復号対象データの量）や符号化データ（復号されなくてはならないデータ）の量を送出することができるという点は有益である。符号化対象データの量又は符号化データの量に基づいて、レンジ符号化後の符号化データ（Ｅ２）３０に存在する情報が、レンジ復号でデータ（Ｄ３）９０が復号されるときに使用されてもよい。また、本開示に従えば、符号化データ（Ｅ２）３０を生成するレンジ符号化において、データの後に追加<EOM>を送出する必要は無い。
【００６４】
確率値が、限定されないが符号化データ（Ｅ２）３０を介して送出される場合、確率値の合計が定義済みである、又は１つ又は複数のデコーダ８０へ予め送出済みである等、既知であるときには、最後の確率値を送出する必要は無い。データの存在するシンボルやエスケープ、<EOM>、実際のシンボルに対する最後の確率値は、それまでに送出済みの全ての値を確率の合計値から差し引くことで算出されてもよい。なお、如何なる場合でも、１つ又は複数のデコーダ８０で確率値の復号が適切に実行可能であるように、合計値は分かっていなくてはならない。最後の確率値を送出しないことによって、幾つかのビットを予めデータサイズから削減しておくこともできる。
【００６５】
本開示の実施例はレンジ符号化に関して提供されてきたが、エンコーダ２０に実装される算術符号化、バイナリ算術符号化についても準用することができる。こうした算術符号化、バイナリ算術符号化がエンコーダ２０に実装される場合、エスケープコードは実際の符号化処理では使用されず、代わりに、後で利用される類似項目用に確率範囲を伝送する仕方を決定する。ただし、こうした方法は、所定のシンボルの存在を伝える可用性信号及び確率値と、その所定のシンボルの確率に関する標示を使用する、前述した本開示の改良方法よりも効率が悪い。これについては次の記載が知られており、参照することができる：「一般に、圧縮率は静的符号化よりも低い。ただし、短い入力データ列に対しては、統計データを送信しない有益性がより有意になり得る。」<http://compressions.sourceforge.net/Arithmetic.html#static> 。したがって、本開示の改良方法は、データ符号化技術において著しい技術的進歩を示している。
【００６６】
本開示に従う改良符号化方法は、パーソナルコンピュータ等のデータ処理・データ生成装置、無線対応携帯コンピュータ、ファブレットコンピュータ、タブレットコンピュータ、スマートフォン、携帯電話（「セルフォン」）、視聴覚機器、デジタルカメラ、ビデオカメラ、科学機器、遺伝子配列解析装置、テレビ受像機、監視装置に用いられてもよい。ただし、これらに限定されない。本改良方法は、特定用途向け集積回路（ASIC）等のデジタルハードウェアに実装されてもよい。あるいは又は加えて、本改良方法は、非一時的機械可読データ記憶媒体に記録された１つ又は複数のソフトウェア製品を用いて実装することもできる。ソフトウェア製品は計算ハードウェアで実行可能である。１つ又は複数のソフトウェア製品は、「ソフトウェアアプリ」として通信ネットワークを介して、例えば携帯電話等の無線対応携帯通信デバイスにダウンロード可能でもよい。エンコーダ２０とそれに対応するデコーダ８０は、コーデック９５としても実装可能である。コーデック９５は例えば、デジタルカメラ等の携帯型信号キャプチャ装置やインターネット対応マルチメディア装置、ゲーム装置、監視カメラ、環境モニタリング装置等に使用することができるが、これらに限定されない。
【００６７】
次に、図２を参照する。図２には、エンコーダ２０でデータ（Ｄ１）１０を符号化してそれに対応する符号化データ（Ｅ２）３０を生成する方法のステップが示されている。 各ステップは示された順に実行されるが、一部のステップは任意選択されるものであり、実行順序も変更可能である。
【表２】
2017511997.tif 000005
【００６８】
１つ又は複数のデコーダ８０では、表２とは逆の処理が実質的に行われる。すなわち、頻度や確率、レンジの情報は、ステップ１００で生成される符号化データ（Ｅ２）３０から抽出され、ステップ１２０からのデータは、符号化データ（Ｅ２）３０で符号化されたシンボルのうち、頻度や確率、レンジの情報を用いて復号されるシンボルと、そうした仕方で復号されない他のシンボルを決定するために利用される。こうした計算の結果は、復号データ（Ｄ３）９０を提供するためにまとめて集められる。１つ又は複数のデコーダ８０は、データＤ１とデータＤ３が相異なるように、トランスコードを実行可能でもよい。こうしたトランスコードは、例えば１つ又は複数のデコーダ８０が相異なり、データＤ３が相異なる表示装置でレンダリングされるものである場合、こうした表示装置用に画素表示解像度、表示アスペクト比等についてカスタマイズ可能になっているという利点がある。
【００６９】
次の図３を参照する。図３には、符号化データ（Ｅ２）３０を復号して復号データ（Ｄ３）９０を生成する復号方法のステップ２００から２４０が示されている。復号データ（Ｄ３）９０はデータ（Ｄ１）１０の再生成版でもよいが、これに限るものではない。 この処理では、ステップ２００で、デコーダ８０は可用性信号、即ち可用性ビットを受け取る。あるいは、符号化方法やインデクスの数、インデクスそのものを受け取ることもできる。さらにステップ２１０で、デコーダ８０は、データ番号６０で伝送された頻度や確率、レンジのテーブル（これらはデータ（Ｅ２）３０に含まれる）を受け取る。デコーダ８０は、これらのテーブルから完全な頻度表や確率表、レンジ表を構成する。ビット「0」のスロットには値「0」を設定するのが有益であるが、必要に応じて値「1」が設定されてもよい。ビット「1」のスロットには、受け取られた頻度や確率、レンジの値が設定される。頻度表が受け取られた場合、それを確率表に変換してレンジ符号化に利用することもできる。当然ながら、エンコーダ２０でもレンジ符号化を用いて効率的な符号化が実行される前に、頻度表を確率表に変換する必要がある。デコーダ８０で確率表を構成した後、ステップ２２０から２４０で、このテーブルから、値の合計値が2の累乗で表わされ、デコーダ８０は受取り済み変換データ５０（データＥ２・３０に含まれる）のレンジ復号を実行することができ、復号出力データ（Ｄ２）９０を生成する。このステップ２００から２４０は、図２のステップ１００から１４０の逆処理と実質的に対応する。
【００７０】
エンコーダ２０とデコーダ８０は幅広いデータ処理装置で利用可能であり、例えば無線通信デバイスやオーディオ装置、視聴覚装置、計算装置、ビデオ会議装置、監視装置、科学測定装置、遺伝子シーケンサ装置、遺伝子配列解析装置、通信システムハードウェア及び／又はソフトウェア、通信ネットワークハードウェア及び／又はソフトウェア等で利用可能である。ただし、これらに限定されるものではない。
【００７１】
前述した本発明の実施形態への修正は、添付の特許請求の範囲に定義される発明の範囲を逸脱しない限りにおいて可能である。本発明の記述と特許請求の範囲で用いられる「含む」，「備える」，「包含する」，「構成される」，「有する」，「存在する」等の表現は、包括的構成であると解釈されることを意図しており、明示的に記載されていないアイテムや部品，構成要素も含まれうることを意図している。単数表現もまた、複数に関連するものと解釈されるべきものである。添付の特許請求の範囲における括弧内の数字は、請求項の理解を助けることを意図したものであり、これらの請求項によって定義される発明の範囲を限定するように解釈されるべきではない。
【図１】
2017511997.tif 000006
【図２】
2017511997.tif 000007
【図３】
2017511997.tif 000008
【手続補正書】
【提出日】平成28年8月3日(2016.8.3)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
入力データ（Ｄ１，１０）を符号化して対応する符号化データ（Ｅ２，３０）を生成するエンコーダ（２０）であって、前記符号化データ（Ｅ２，３０）は、該符号化データ（Ｅ２，３０）で表わされるべき複数のシンボルそれぞれの頻度、確率又はレンジの値に関する情報を含み、前記エンコーダ（２０）は、前記シンボルの頻度、確率又はレンジの値に関する前記情報が前記符号化データ（Ｅ２，３０）に含まれるか否かを示す追加情報を、該符号化データ（Ｅ２，３０）に含めるように動作可能である、
エンコーダ（２０）。
【請求項２】
前記シンボルの頻度、確率又はレンジの値に関する前記情報が前記符号化データ（Ｅ２，３０）に含まれるか否かを示す追加情報であって、単一の可用性ビット情報として表わされる、該追加情報を、該符号化データ（Ｅ２，３０）に含めるように動作可能である、請求項１に記載のエンコーダ（２０）。
【請求項３】
前記符号化データ（Ｅ２，３０）に前記頻度、確率又はレンジの値に関する前記情報が含まれることを、単一の可用性ビット値「１」を用いて表わし、該符号化データ（Ｅ２，３０）に該頻度、確率又はレンジの値に関する前記情報が含まれていないことを、単一の可用性ビット値「０」を用いて表わすように動作可能である、請求項２に記載のエンコーダ（２０）。
【請求項４】
前記符号化データ（Ｅ２，３０）で表わされるべきシンボルの頻度、確率又はレンジの値に関する前記情報は、符号化対象データ（Ｄ１，１０）の１つ又は複数の特性の関数として、前記エンコーダ（２０）によって動的に変更される、請求項１から３の何れかに記載のエンコーダ（２０）。
【請求項５】
前記１つ又は複数の特性は、前記データ（Ｄ１，１０）の種類、該データ（Ｄ１，１０）のコンテンツ及び／又は該データ（Ｄ１，１０）の統計情報の少なくとも１つを含む、請求項４に記載のエンコーダ（２０）。
【請求項６】
前記符号化対象データ（Ｄ１，１０）を複数の部分に分割し、該部分のそれぞれに対して別個に対応する追加情報であって、前記シンボルの頻度、確率又はレンジの値に関する前記情報が前記符号化データ（Ｅ２，３０）に含まれるか否かを示す、該追加情報を生成するように動作可能である、請求項４又は５に記載のエンコーダ（２０）。
【請求項７】
前記エンコーダ（２０）は、前記データ（Ｄ１，１０）において生じる最小値及び最大値を決定するために該データ（Ｄ１，１０）を解析するように動作可能であり、前記最小値及び最大値を表わす情報は、該エンコーダ（２０）によって前記符号化データ（Ｅ２，３０）に含められ、該最小値及び最大値は、レンジ符号化が用いられる場合、可能性のある利用可能なシンボル値の範囲を制限する、請求項１から６の何れかに記載のエンコーダ（２０）。
【請求項８】
可用性信号を用いずに、前記データ（Ｄ１，１０）に存在する先頭シンボル及び／又は最後尾シンボルを前記符号化データ（Ｅ２，３０）に表わすように動作可能である、請求項７に記載のエンコーダ（２０）。
【請求項９】
前記符号化対象データ（Ｄ１，１０）にレンジ符号化を適用して前記符号化データ（Ｅ２，３０）を生成する前に、該データ（Ｄ１，１０）のエントロピーを修正するように動作可能である、請求項１から８の何れかに記載のエンコーダ（２０）。
【請求項１０】
前記エンコーダ（２０）は、前記データ（Ｄ１，１０）を符号化するように動作可能であり、該データ（Ｄ１，１０）は、録音音声信号、遺伝子配列データ、録画ビデオ信号、静止画像、テキストデータ、感震データ、センサ信号データ、アナログ−デジタル変換（ＡＤＣ）データ、生体信号データ、カレンダーデータ、経済データ、数学的データの少なくとも１つに対応する、請求項１から９の何れかに記載のエンコーダ（２０）。
【請求項１１】
エンコーダ（２０）で入力データ（Ｄ１，１０）を符号化して対応する符号化データ（Ｅ２，３０）を生成する方法であって、前記符号化データ（Ｅ２，３０）は、該符号化データ（Ｅ２，３０）で表わされるべき複数のシンボルそれぞれの頻度、確率又はレンジの値に関する情報を含み、前記方法は：
前記シンボルの頻度、確率又はレンジの値に関する前記情報が前記符号化データ（Ｅ２，３０）に含まれるか否かを示す追加情報を、該符号化データ（Ｅ２，３０）に含めるために、前記エンコーダ（２０）を使用すること
を含む、方法。
【請求項１２】
前記シンボルの頻度、確率又はレンジの値に関する前記情報が前記符号化データ（Ｅ２，３０）に含まれるか否かを示す追加情報であって、単一の可用性ビット情報として表わされる、該追加情報を、該符号化データ（Ｅ２，３０）に含めるために、前記エンコーダ（２０）を使用することを更に含む、請求項１１に記載の方法。
【請求項１３】
前記符号化データ（Ｅ２，３０）に前記頻度、確率又はレンジの値に関する前記情報が含まれることを、単一の可用性ビット値「１」を用いて表わし、該符号化データ（Ｅ２，３０）に該頻度、確率又はレンジの値に関する前記情報が含まれていないことを、単一の可用性ビット値「０」を用いて表わすために、前記エンコーダ（２０）を使用することを更に含む、請求項１２に記載の方法。
【請求項１４】
前記符号化データ（Ｅ１２，３０）で表わされるべきシンボルの頻度、確率又はレンジの値に関する前記情報を、前記符号化対象データ（Ｄ１，１０）の１つ又は複数の特性の関数として動的に変更するために、前記エンコーダ（２０）を使用することを含む、請求項１１から１３の何れかに記載の方法。
【請求項１５】
前記符号化対象データ（Ｄ１，１０）を複数の部分に分割し、該部分のそれぞれに対して別個に対応する追加情報であって、前記シンボルの頻度、確率又はレンジの値に関する前記情報が前記符号化データ（Ｅ２，３０）に含まれるか否かを示す、該追加情報を生成するために、前記エンコーダ（２０）を使用することを含む、請求項１４に記載の方法。
【請求項１６】
前記方法は前記データ（Ｄ１，１０）を符号化することを含み、該データ（Ｄ１，１０）は、録音音声信号、遺伝子配列データ、録画ビデオ信号、静止画像、テキストデータ、感震データ、センサ信号データ、アナログ−デジタル変換（ＡＤＣ）データ、生体信号データ、カレンダーデータ、経済データ、数学的データの少なくとも１つに対応する、請求項１１から１５の何れかに記載の方法。
【請求項１７】
復号データ（Ｄ３，９０）を生成するために、請求項１から１０の何れかに記載のエンコーダ（２０）によって生成された符号化データ（Ｅ２，３０）を復号する、デコーダ（８０）。
【請求項１８】
（ａ）可用性信号を受け取ることと；
（ｂ）前記符号化データ（Ｅ２，３０）で伝送された頻度、確率又はレンジのテーブルを受け取ることと；
（ｃ）前記（ａ）及び（ｂ）から、完全な頻度表、確率表又はレンジ表を構成することと；
（ｄ）前記符号化データ（Ｅ２，３０）を復号して出力データ（Ｄ３，９０）を生成するために、前記完全な頻度表、確率表又はレンジ表を使用すること
を実行するように動作可能であるデータ処理ハードウェアを備える、請求項１７に記載のデコーダ（８０）。
【請求項１９】
対応するトランスコードデータを生成するために、前記復号出力データ（Ｄ３）にトランスコードを実行するように動作可能である、請求項１７又は１８に記載のデコーダ（８０）。
【請求項２０】
デコーダ（８０）で符号化データ（Ｅ２，３０）を復号する方法であって、請求項１１から１６の何れかに記載の方法とは逆の処理を実行することを含む、方法。
【請求項２１】
（ａ）可用性信号を受け取ることと；
（ｂ）前記符号化データ（Ｅ２，３０）で伝送された頻度、確率又はレンジのテーブルを受け取ることと；
（ｃ）前記処理（ａ）及び（ｂ）から、完全な頻度表、確率表又はレンジ表を構成することと；
（ｄ）前記符号化データ（Ｅ２，３０）を復号して出力データ（Ｄ３，９０）を生成するために、前記完全な頻度表、確率表又はレンジ表を使用すること
を含む、請求項２０に記載の方法。
【請求項２２】
対応するトランスコードデータを生成するために、前記復号出力データ（Ｄ３）にトランスコードを実行することを含む、請求項２０又は２１に記載の方法。
【請求項２３】
請求項１から１０の何れかに記載の少なくとも１つのエンコーダ（２０）と、請求項１７から１９の何れかに記載の少なくとも１つのデコーダ（８０）を備える、コーデック（２０，８０，９５）。
【請求項２４】
エンコーダの処理手段に実行されると、前記エンコーダに、請求項１１から１６の何れかに記載の方法を遂行させるプログラム命令を備える、コンピュータプログラム。
【請求項２５】
エンコーダの処理手段に実行されると、前記エンコーダに、請求項２０に記載の方法を遂行させるプログラム命令を備える、コンピュータプログラム。
【国際調査報告】
2017511997.tif 000009
2017511997.tif 000010
2017511997.tif 000011