(57)【要約】  ランレングス符号化における非０信号の位置を効率良く求めることができる装置を提供する。符号化対象となる複数の信号をそれぞれ区別するためにインデックスが付与された信号を格納する第一記憶手段（１１０）と、第一記憶手段に格納された前記信号のうち０でない信号の第一インデックスを計算する第一インデックス計算手段（１２１）と、ベースインデックスと前記第一インデックスとから第二インデックスを計算する第二インデックス計算手段（１２２）と、第二記憶手段（１１０）に格納されたインデックスの値に基づいて、前記第二インデックスを格納すべき第二記憶手段の格納位置を探索する第二インデックス格納位置探索手段（１２３）と、前記第二インデックス格納位置探索手段が探索した格納位置に基づいて、前記第二インデックスを前記第二記憶手段へ格納する第二インデックス格納手段（１２４）と、前記ベースインデックスを前記第二インデックス計算手段へ与え、前記第一インデックス計算手段と前記第二インデックス計算手段と前記第二インデックス格納位置探索手段と第二インデックス格納手段とを動作させる制御手段（１３０）と、を備える。
2008066050.tif 000002
【特許請求の範囲】
【請求項１】
符号化対象となる信号をランレングス符号化する符号化装置であって、
符号化対象となる複数の信号をそれぞれ区別するためにインデックスが付与された信号を格納する第一記憶手段と、
インデックスを格納するための第二記憶手段と、
前記第一記憶手段に格納された前記信号のうち非０信号の第一インデックスを計算する第一インデックス計算手段と、
ベースインデックスと前記第一インデックスとから第二インデックスを計算する第二インデックス計算手段と、
前記第二記憶手段に格納されたインデックスの値にもとづいて、前記第二インデックスを格納すべき前記第二記憶手段における格納位置を探索する第二インデックス格納位置探索手段と、
前記第二インデックス格納位置探索手段が探索した格納位置にもとづいて、前記第二インデックスを前記第二記憶手段へ格納する第二インデックス格納手段と、
前記ベースインデックスを前記第二インデックス計算手段へ与えるとともに、前記第一インデックス計算手段、前記第二インデックス計算手段、前記第二インデックス格納位置探索手段、及び第二インデックス格納手段の動作をそれぞれ制御する制御手段と、
を備える、ことを特徴とする符号化装置。
【請求項２】
請求項１に記載の符号化装置において、
前記第二インデックス格納位置探索手段は前記第二インデックスが前記第二記憶手段へ昇順または降順に格納されるような格納位置を探索する手段、
を備える、ことを特徴とする符号化装置。
【請求項３】
請求項２に記載の符号化装置において、
前記第二記憶手段へ格納された非０信号のインデックスの隣接する要素間の差を計算する手段と、
前記要素間の差から１を減算することによって非０信号の前にある０の数を求める手段と、
を備える、ことを特徴とする符号化装置。
【請求項４】
請求項１乃至３のいずれか一に記載の符号化装置を構成しているプロセッサ。
【請求項５】
レジスタファイルと、非０信号検出ユニットと、命令デコーダとを備え、
ランレングス符号化の対象となるＳ個の信号に対して０からＳ−１までのインデックスを付けて、前記Ｓ個の信号から取り出されたＮ個（ただし、ＮはＳ以下、２以上の整数）の信号ｓ（ｎ）（ｎ＝０〜Ｎ−１）が前記レジスタファイルの第一のレジスタに格納され、
前記Ｎ個の信号の信号ｓ（０）の前記インデックスをベースインデックスとして、
前記レジスタファイルの第二のレジスタにはＫ個（ただし、Ｋは信号総数Ｓよりも小の正整数）の初期化されたインデックスｘ（ｋ）（ｋ＝０〜Ｋ−１）が予め格納されており、
デコードした命令が非０信号検出命令であるときに前記命令デコーダは前記非０信号検出ユニットを動作させ、
前記命令デコーダは前記ベースインデックスを前記非０信号検出ユニットに与え、
前記非０信号検出ユニットは、
前記レジスタファイルの前記第一のレジスタから信号ｓ（ｎ）（ｎ＝０〜Ｎ−１）を読み込み、前記ベースインデックスを用いて、前記信号ｓ（ｎ）に含まれる非０信号のインデックスｐ（ｍ）（ｍ＝０〜Ｍ−１、Ｍは信号ｓ（ｎ）に含まれる非０信号の数）を計算する第一の手段と、
前記レジスタファイルの前記第二のレジスタに格納されたインデックスｘ（ｋ）（ｋ＝０〜Ｋ−１）と前記非０信号のインデックスｐ（ｍ）とを用いて、前記ｐ（ｍ）を前記ｘ（ｋ）へ追加したインデックスを更新後のインデックスｙ（ｋ）（ｋ＝０〜Ｋ−１）とする第二の手段と、
前記更新後のインデックスｙ（ｋ）（ｋ＝０〜Ｋ−１）を前記第二のレジスタへ書き込む第三の手段と、
を備える、ことを特徴とするプロセッサ。
【請求項６】
前記第二の手段は、前記インデックスｘ（ｋ）（ｋ＝０〜Ｋ−１）において最もｋが小さい負のインデックスｘ（ｋ）をｘ（Ｇ）として、前記更新後のインデックスｙ（ｋ）（ｋ＝０〜Ｋ−１）を、
０＜＝ｋ＜Ｇの場合に、
ｙ（ｋ）＝ｘ（ｋ）
とし、
Ｇ＜＝ｋ＜（Ｇ＋Ｍ）の場合に、
ｙ（ｋ）＝ｐ（ｋ−Ｇ）
とし、  
（Ｇ＋Ｍ）＜＝ｋ＜Ｋの場合に、
ｙ（ｋ）＝ｘ（ｋ）
とする、ことを特徴とする請求項５記載のプロセッサ。
【請求項７】
符号化対象のＳ個の信号をＮ個ずつＬ組にわけ、
前記第二のレジスタに所定値を格納して前記インデックスｘ（ｋ）を初期化し、
変数ｉ＝０として０からＬ−１までｉを１ずつ増加させながら、
ｉ番目のＮ個の信号ｓ（ｎ）（ｎ＝０〜Ｎ−１）を前記第一のレジスタへ格納し、
前記ベースインデックスをＮ×ｉとして、前記非０信号検出ユニットを動作させ、
前記第一のレジスタに格納された前記信号ｓ（ｎ）の非０信号のインデックスを前記第二のレジスタへ追加し、
上記処理を繰り返す、ことを特徴とする請求項５又は６に記載のプロセッサ。
【請求項８】
前記信号ｓ（ｎ）の非０信号のインデックスｘ（ｋ）に対して番号ｋが大きくなる方向へｘ（ｋ）を１要素分ずらしたものをａ（ｋ）とし、
ｘ（ｋ）とａ（ｋ）の差ｂ（ｋ）＝ｘ（ｋ）−ａ（ｋ）
（ｋ＝０〜Ｎ−１）を求め、
次にｂ（ｋ）から２×Ｎとの和ｃ（ｋ）＝ｂ（ｋ）＋２×Ｎ  （ｋ＝０〜Ｎ−１）を求め、
次にｃ（ｋ）の所定下位ビットを抽出したものをｄ（ｋ）として
ｅ（ｋ）＝ｄ（ｋ）−１  （ｋ＝０〜Ｎ−１）
を求め、
番号ｋが小さくなる方向へｅ（ｋ）を１要素分ずらしたものをｚ（ｋ）として、
z（ｋ）をｘ（ｋ）の各要素に対応するランレングスとする、ことを特徴とする請求項５乃至７のいずれか一に記載のプロセッサ。
【請求項９】
符号化対象となる信号をランレングス符号化する符号化方法であって、
符号化対象となる複数の信号をそれぞれ区別するためにインデックスが付与された信号を格納する第一記憶手段に格納された前記信号のうち非０信号の第一インデックスを計算する第一インデックス計算工程と、
ベースインデックスと前記第一インデックスとから第二インデックスを計算する第二インデックス計算工程と、
インデックスを格納する第二記憶手段に格納されたインデックスの値にもとづいて、前記第二インデックスを格納すべき前記第二記憶手段における格納位置を探索する第二インデックス格納位置探索手工程と、
前記第二インデックス格納位置探索工程で探索された格納位置にもとづいて、前記第二インデックスを前記第二記憶手段へ格納する第二インデックス格納工程と、
前記ベースインデックスを前記第二インデックス計算工程へ与えるとともに、前記第一インデックス計算工程、前記第二インデックス計算工程、前記第二インデックス格納位置探索工程、及び第二インデックス格納工程の動作をそれぞれ制御する工程と、
を含む、ことを特徴とする符号化方法。
【請求項１０】
請求項９に記載の符号化方法において、
前記第二インデックス格納位置探索工程では、前記第二インデックスが前記第二記憶手段へ昇順または降順に格納されるような格納位置を探索する、ことを特徴とする符号化方法。
【請求項１１】
請求項１０に記載の符号化方法において、
前記第二記憶手段へ格納された非０信号のインデックスの隣接する要素間の差を計算する工程と、
前記要素間の差から１を減算することによって非０信号の前にある０の数を求める工程と、
を含む、ことを特徴とする符号化方法。
【請求項１２】
符号化対象となる信号をランレングス符号化する符号化装置を構成するコンピュータに、
符号化対象となる複数の信号をそれぞれ区別するためにインデックスが付与された信号を格納する第一記憶手段に格納された前記信号のうち非０信号の第一インデックスを計算する第一インデックス計算処理と、
ベースインデックスと前記第一インデックスとから第二インデックスを計算する第二インデックス計算処理と、
インデックスを格納する第二記憶手段に格納されたインデックスの値にもとづいて、前記第二インデックスを格納すべき前記第二記憶手段における格納位置を探索する第二インデックス格納位置探索手処理と、
前記第二インデックス格納位置探索処理で探索された格納位置にもとづいて、前記第二インデックスを前記第二記憶手段へ格納する第二インデックス格納処理と、
前記ベースインデックスを前記第二インデックス計算処理へ与えるとともに、前記第一インデックス計算処理、前記第二インデックス計算処理、前記第二インデックス格納位置探索処理、及び第二インデックス格納処理の動作をそれぞれ制御する処理と、
を実行させるプログラム。
【請求項１３】
請求項１２に記載のプログラムにおいて、
前記第二インデックス格納位置探索処理は、前記第二インデックスが前記第二記憶手段へ昇順または降順に格納されるような格納位置を探索する、ことを特徴とするプログラム。
【請求項１４】
請求項１３に記載のプログラムにおいて、
前記第二記憶手段へ格納された非０信号のインデックスの隣接する要素間の差を計算する処理と、
前記要素間の差から１を減算することによって非０信号の前にある０の数を求める処理と、
を前記コンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願の記載］
本発明は、日本国特許出願：特願２００６−３２０２７８号（２００６年１１月２８日出願）の優先権主張に基づくものであり、同出願の全記載内容は引用をもって本書に組み込み記載されているものとする。
本発明は圧縮符号化技術に関し、特に画像や音声の圧縮符号化において使用されるランレングス符号化に好適な符号化装置と方法及びプロセッサ並びにプログラムに関する。
【背景技術】
【０００２】
ランレングス符号化とは画像や音楽の信号を圧縮する際に用いられる符号化方式である。例えば、ＪＰＥＧ（Joint Photographic Experts Group）、ＭＰＥＧ−２(Moving Picture Experts Group Phase-2)、ＭＰＥＧ−４(Moving Picture Experts Group Phase-4)、Ｈ．２６４などの画像符号化方式はランレングス符号化を用いている。【０００３】
ランレングス符号化は０が頻繁に出現する信号の圧縮に適している。ランレングス符号化は非０信号の前に出現する０の数とその非０信号の値とを一組の情報として符号化する。【０００４】
ビデオ符号化方式Ｈ．２６４における４ｘ４ブロックの符号化方法を例にとって、ランレングス符号化について説明する。図５はＨ．２６４における４ｘ４ブロックの符号化手順を表す図である。図５（Ａ）において４ｘ４ブロックはＤＣＴ（Discrete Cosine Transform）後の係数である。図５（Ｂ）に示すように、４ｘ４ブロックにある係数をジグザグにスキャンして、図５（Ｃ）に示ように係数を並び替える。【０００５】
並び替えた係数の中から、非０係数と０係数を見つけて、
（１）各非０係数の前の０の数、
（２）各非０係数の値、
（３）非０係数の個数、
などの情報を取り出す。【０００６】
上記の（１）、（２）、（３）を効率よく取り出すには、非０係数の位置を見つければよい。【０００７】
非０係数の位置とはジグザグにスキャンして並び変えた係数の並び順を表すインデックスである。最初の係数のインデックスを０とし、その次の係数のインデックスを１、その次を２、・・・とする。【０００８】
非０係数のインデックスがわかれば、非０係数の数や、非０係数の前の０の数を計算することができる。【０００９】
しかし、従来のＣＰＵ（Central Processing Unit）やＤＳＰ（Digital  Signal Processor）などのプロセッサは高速に非０係数のインンデックスを求めることができない。従来のＣＰＵやＤＳＰはランレングス符号化の高速処理に不向きである。【００１０】
ＣＰＵやＤＳＰなどのプロセッサでは、通常、係数を順番にスキャンすることによって非０係数のインデックスを見つける。係数を順番にスキャンすると、係数の個数分の手間がかかる。そのため、従来のプロセッサは非０係数のインデックスを効率よく見つけることができない。【００１１】
０の数を数える処理が必要なランレングス符号化は逐次的な処理である。このため、ランレングス符号化を並列化することは一般的に困難である。【００１２】
もし０の数を数える処理を並列化できれば、プロセッサにおけるランレングス符号化を従来よりも高速化できる。【００１３】
なお、０の数を数える処理を並列化する方法が特許文献１に開示されている。特許文献１に開示された方法は、信号を″０か否か″という１ビットのフラグで表し、複数個のフラグを一つのキーとして使ってランレングス・テーブルからランレングスを求める。つまり、ランレングスを求めるためにランレングス・テーブルを使用する。特許文献１によれば、ランレングス・テーブルには２５６要素の情報が格納される。【００１４】
信号を順番にスキャンしながらランレングスを求めるよりも、特許文献１の方法でランレングスを求める方が少ないステップ数でランレングスを求めることができる。【００１５】
一方、特許文献２にはランレングス符号化を実行する符号化装置と方法が開示されている。特許文献２のランレングス符号化装置は、
（ａ）入力信号のゼロ判定、
（ｂ）ランレングス計算、
という手順でランレングスを求める。（ａ）の処理は全ての入力信号について０か否かを判定し、その判定結果を記憶しておく。そして、その判定結果に基づいて非０信号の前に存在する０の数を計算する。【００１６】
【特許文献１】特開２００３−３３０９１１号公報
【特許文献２】特開２００４−１６６０８３号公報
【発明の開示】
【発明が解決しようとする課題】
【００１７】
以上の特許文献１及び２の開示事項は、本書に引用をもって繰り込み記載されているものとする。以下に本発明による関連技術の分析を与える。
上記した特許文献１の方法は、ランレングス・テーブルを必要とする。ランレングス・テーブルは２５６要素の情報をもつ比較的小さなテーブルではあるものの、ランレングス・テーブルを参照する動作はプロセッサのキャッシュミスヒットを起こす要因となる。また特許文献１の方法でも、ランレングスを求めるのに多くのステップが必要である。例えば、特許文献１によると（特許文献１の図７と関連説明参照）、一つのランレングスを求めるために１０ステップ程度の処理が必要となる。【００１８】
一方、上記した特許文献２の符号化装置の場合、全ての入力信号について、ゼロ判定結果を記憶手段へ保存する必要がある。全ての入力信号のゼロ判定結果を保存する場合、入力信号の最大数が予めわかっている必要がある。さらに、全ての入力信号のゼロ判定結果を保存する記憶手段が必要となる。入力信号の数が多い場合、記憶手段の容量も大きくなる。一例として入力信号の数が１６ｘ１６＝２５６個の場合、２５６ビットのゼロ判定結果を格納する記憶手段が必要となる。【００１９】
しかしながら、非０信号のインデックスだけを記憶することにすれば、その記憶手段の容量を小さくできる。【００２０】
上記したように、従来のプロセッサ／符号化装置はランレングス符号化を効率良く実行できない、という問題がある。【００２１】
具体的には、
ランレングス・テーブルが必要である、
ランレングスを求めるためにステップ数が多い、
全信号のゼロ判定結果を格納するための記憶手段が必要である、
等の問題がある。【００２２】
したがって、本発明の主たる目的は、ランレングス符号化における非０信号の位置を効率良く求めることができる装置と方法及びプロセッサ、プログラムを提供することにある。
【課題を解決するための手段】
【００２３】
本願で開示される発明は、前記目的を達成するため、概略以下の構成とされる。【００２４】
本発明の符号化装置は、符号化対象となる信号をランレングス符号化する符号化装置であって、符号化対象となる複数の信号をそれぞれ区別するためにインデックスが付与された信号を格納する第一記憶手段と、
インデックスを格納するための第二記憶手段と、
前記第一記憶手段に格納された前記信号のうち非０信号の第一インデックスを計算する第一インデックス計算手段と、
ベースインデックスと前記第一インデックスとから第二インデックスを計算する第二インデックス計算手段と、
前記第二記憶手段に格納されたインデックスの値にもとづいて、前記第二インデックスを格納すべき前記第二記憶手段における格納位置を探索する第二インデックス格納位置探索手段と、
前記第二インデックス格納位置探索手段が探索した格納位置にもとづいて、前記第二インデックスを前記第二記憶手段へ格納する第二インデックス格納手段と、
前記ベースインデックスを前記第二インデックス計算手段へ与えるとともに、前記第一インデックス計算手段、前記第二インデックス計算手段、前記第二インデックス格納位置探索手段、及び第二インデックス格納手段の動作をそれぞれ制御する制御手段と、
を備える。【００２５】
本発明の符号化装置は、前記第二インデックス格納位置探索手段は前記第二インデックスが前記第二記憶手段へ昇順または降順に格納されるような格納位置を探索する手段、を備えてもよい。本発明の符号化装置は、前記第二記憶手段へ格納された非０信号のインデックスの隣接する要素間の差を計算する手段と、
前記要素間の差から１を減算することによって非０信号の前にある０の数を求める手段と、を備えていてもよい。【００２６】
本発明のプロセッサは、レジスタファイルと、非０信号検出ユニットと、命令デコーダとを備え、
ランレングス符号化の対象となるＳ個の信号に対して０からＳ−１までのインデックスを付けて、前記Ｓ個の信号から取り出されたＮ個（ただし、ＮはＳ以下、２以上の整数）の信号ｓ（ｎ）（ｎ＝０〜Ｎ−１）が前記レジスタファイルの第一のレジスタに格納され、
前記Ｎ個の信号の信号ｓ（０）の前記インデックスをベースインデックスとして、
前記レジスタファイルの第二のレジスタにはＫ個（ただし、Ｋは信号総数Ｓよりも小の正整数）の初期化されたインデックスｘ（ｋ）（ｋ＝０〜Ｋ−１）が予め格納されており、
デコードした命令が非０信号検出命令であるときに前記命令デコーダは前記非０信号検出ユニットを動作させ、
前記命令デコーダは前記ベースインデックスを前記非０信号検出ユニットに与え、
前記非０信号検出ユニットは、
前記レジスタファイルの前記第一のレジスタから信号ｓ（ｎ）（ｎ＝０〜Ｎ−１）を読み込み、前記ベースインデックスを用いて、前記信号ｓ（ｎ）に含まれる非０信号のインデックスｐ（ｍ）（ｍ＝０〜Ｍ−１、Ｍは信号ｓ（ｎ）に含まれる非０信号の数）を計算する第一の手段と、
前記レジスタファイルの前記第二のレジスタに格納されたインデックスｘ（ｋ）（ｋ＝０〜Ｋ−１）と前記非０信号のインデックスｐ（ｍ）とを用いて、前記ｐ（ｍ）を前記ｘ（ｋ）へ追加したインデックスを更新後のインデックスｙ（ｋ）（ｋ＝０〜Ｋ−１）とする第二の手段と、
前記更新後のインデックスｙ（ｋ）（ｋ＝０〜Ｋ−１）を前記第二のレジスタへ書き込む第三の手段と、
を備える。【００２７】
本発明に係るプロセッサにおいて、前記第二の手段は、前記インデックスｘ（ｋ）（ｋ＝０〜Ｋ−１）において最もｋが小さい負のインデックスｘ（ｋ）をｘ（Ｇ）として、前記更新後のインデックスｙ（ｋ）（ｋ＝０〜Ｋ−１）を、
０＜＝ｋ＜Ｇの場合に、
ｙ（ｋ）＝ｘ（ｋ）
とし、
Ｇ＜＝ｋ＜（Ｇ＋Ｍ）の場合に、
ｙ（ｋ）＝ｐ（ｋ−Ｇ）
とし、  
（Ｇ＋Ｍ）＜＝ｋ＜Ｋの場合に、
ｙ（ｋ）＝ｘ（ｋ）
としてもよい。【００２８】
本発明に係るプロセッサにおいて、符号化対象のＳ個の信号をＮ個ずつＬ組にわけ、
前記第二のレジスタに所定値を格納して前記インデックスｘ（ｋ）を初期化し、
変数ｉ＝０として０からＬ−１までｉを１ずつ増加させながら、
ｉ番目のＮ個の信号の組ｓ（ｎ）（ｎ＝０〜Ｎ−１）を前記第一のレジスタへ格納し、
前記ベースインデックスをＮ×ｉとして前記非０信号検出ユニットを動作させ、
前記第一のレジスタに格納された前記信号ｓ（ｎ）の非０信号のインデックスを前記第二のレジスタへ追加し、
上記処理を繰り返す構成としてもよい。【００２９】
本発明に係るプロセッサにおいて、前記信号ｓ（ｎ）の非０信号のインデックスｘ（ｋ）に対して番号ｋが大きくなる方向へｘ（ｋ）を１個分ずらしたものをａ（ｋ）とし、
ｘ（ｋ）とａ（ｋ）の差ｂ（ｋ）＝ｘ（ｋ）−ａ（ｋ）  （ｋ＝０〜Ｎ−１）を求め、
次にｂ（ｋ）から２×Ｎとの和ｃ（ｋ）＝ｂ（ｋ）＋２×Ｎ  （ｋ＝０〜Ｎ−１）を求め、
次にｃ（ｋ）の所定下位ビットを抽出したものをｄ（ｋ）として  ｅ（ｋ）＝ｄ（ｋ）−１  （ｋ＝０〜Ｎ−１）  を求め、
番号ｋが小さくなる方向へｅ（ｋ）を１個分ずらしたものをｚ（ｋ）として、
z（ｋ）をｘ（ｋ）の各要素に対応するランレングスとする、という構成にしてもよい。
本発明によれば、符号化対象となる信号をランレングス符号化する符号化方法であって、符号化対象となる複数の信号をそれぞれ区別するためにインデックスが付与された信号を格納する第一記憶手段に格納された前記信号のうち非０信号の第一インデックスを計算する第一インデックス計算工程と、
ベースインデックスと前記第一インデックスとから第二インデックスを計算する第二インデックス計算工程と、
インデックスを格納する第二記憶手段に格納されたインデックスの値にもとづいて、前記第二インデックスを格納すべき前記第二記憶手段における格納位置を探索する第二インデックス格納位置探索手工程と、
前記第二インデックス格納位置探索工程で探索された格納位置にもとづいて、前記第二インデックスを前記第二記憶手段へ格納する第二インデックス格納工程と、
前記ベースインデックスを前記第二インデックス計算工程へ与えるとともに、前記第一インデックス計算工程、前記第二インデックス計算工程、前記第二インデックス格納位置探索工程、及び第二インデックス格納工程の動作をそれぞれ制御する工程と、
を含む符号化方法が提供される。
本発明によれば、符号化対象となる信号をランレングス符号化する符号化装置を構成するコンピュータに、
符号化対象となる複数の信号をそれぞれ区別するためにインデックスが付与された信号を格納する第一記憶手段に格納された前記信号のうち非０信号の第一インデックスを計算する第一インデックス計算処理と、
ベースインデックスと前記第一インデックスとから第二インデックスを計算する第二インデックス計算処理と、
インデックスを格納するための第二記憶手段に格納されたインデックスの値にもとづいて、前記第二インデックスを格納すべき前記第二記憶手段における格納位置を探索する第二インデックス格納位置探索手処理と、
前記第二インデックス格納位置探索処理で探索された格納位置にもとづいて、前記第二インデックスを前記第二記憶手段へ格納する第二インデックス格納処理と、
前記ベースインデックスを前記第二インデックス計算処理へ与えるとともに、前記第一インデックス計算処理、前記第二インデックス計算処理、前記第二インデックス格納位置探索処理、及び第二インデックス格納処理の動作をそれぞれ制御する処理と、
を実行させるプログラムが提供される。
【発明の効果】
【００３０】
本発明によれば、ランレングス符号化における非０信号の位置を求める処理を効率良く実行できる。その理由は、ランレングス符号化における非０信号の位置を求めるにあたり、ランレングス・テーブルを用いずに、従来装置と比べて少ないステップ数で実行できるようにしたためである。本発明によれば、全ての信号のゼロ判定結果を格納するための記憶手段を不用としている。
【図面の簡単な説明】
【００３１】
【図１】本発明の一実施例の構成を表す図である。
【図２】本発明の一実施例の非０信号検出ユニットの動作を説明する図である。
【図３】本発明の一実施例の動作を説明する図である。
【図４】本発明の一実施例において、Ｎ個より多い数の信号から非０信号のインデックスを求める手順を説明するための図である。
【図５】Ｈ．２６４における４ｘ４ブロックの符号化手順を表す図である。
【図６】本発明の一実施例において、非０信号のインデックスからランレングスを求める手順を説明するための図である。
【符号の説明】
【００３２】
１１０  レジスタファイル
１１１、１１２  レジスタ
１２０  非０信号検出ユニット
１２１  第一インデックス計算ユニット
１２２  第二インデックス計算ユニット
１２３  第二インデックス格納位置探索ユニット
１２４  第二インデックス格納ユニット
１３０  命令デコーダ
【発明を実施するための最良の形態】
【００３３】
上記した本発明についてさらに詳細に説明すべく、添付図面を参照して以下に説明する。本発明は、ランレングス符号の符号化器として動作可能なプロセッサであって、Ｎ個の信号を格納するための第一記憶手段（図１の１１０、図２の１１１）と、複数のインデックスを格納するための第二記憶手段（図１の１１０、図２の１１２）と、第一記憶手段に格納されたＮ個の信号から非０信号の第一インデックスを求める第一インデックス計算ユニット（図１の１２１）と、ベースインデックスと第一インデックスとの和を第二インデックスとする第二インデックス計算ユニット（図１の１２２）と、第二記憶手段（図１の１１０、図２の１１２）に格納されたインデックスの値にもとづいて第二インデックスを格納すべき第二記憶手段（図１の１１０、図２の１１２）の格納位置を探索する第二インデックス格納位置探索ユニット（図１の１２３）と、第二インデックス格納位置探索ユニット（図１の１２３）が探索した格納位置にもとづいて第二インデックスを第二記憶手段（図２の１１２）へ格納する第二インデックス格納ユニット（図１の１２４）と、プロセッサに与えられた命令に応答して、命令語に対応するベースインデックスを第二インデックス計算ユニットへ与え、第一インデックス計算ユニットと第二インデックス計算ユニットと第二インデックス格納位置探索ユニットと第二インデックス格納ユニットとの動作を制御する命令デコーダ（図１の１３０）と、を備えている。以下実施例に即して詳細に説明する。
【実施例】
【００３４】
図１は、本発明の一実施例の構成を示す図である。図１を参照すると、本実施例のプロセッサは、レジスタファイル１１０と、非０信号検出ユニット１２０と、命令デコーダ１３０を備え、ランレングス符号化を実行する。【００３５】
レジスタファイル１１０は、複数のレジスタからなる。レジスタファイル１１０のレジスタにランレングス符号化に必要な以下の二種類のデータを格納する。【００３６】
・ランレングス符号化の対象となるＮ個の信号。【００３７】
・ランレングス符号化の過程で生成される非０信号のインデックス。【００３８】
非０信号検出ユニット１２０は、レジスタファイル１１０からランレングス符号化の対象となるＮ個の信号と、非０信号のインデックスとを読み込む。【００３９】
非０信号検出ユニット１２０は命令デコーダ１３０から与えられたベースインデックスを取り込み、Ｎ個の信号の非０信号のインデックスを求め、求めたインデックスに基づいて、レジスタファイル１１０から読み込んだインデックスを更新し、更新したインデックスをレジスタファイル１１０へ格納する。【００４０】
非０信号検出ユニット１２０は、第一インデックス計算ユニット１２１と、第二インデックス計算ユニット１２２と、第二インデックス格納位置探索ユニット１２３と、第二インデックス格納ユニット１２４とを備えている。【００４１】
第一インデックス計算ユニット１２１は、レジスタファイル１１０からランレングス符号化の対象となるＮ個の信号と、非０信号のインデックスと、を読み込み、Ｎ個の信号のなかの非０信号の第一インデックスを求める。【００４２】
第二インデックス計算ユニット１２２は、第一インデックス計算ユニット１２１で求められた第一インデックスと、プロセッサの命令デコーダ１３０から与えられたベースインデックスとの和を計算し、第一インデックスとベースインデックスとの和を第二インデックスとする。【００４３】
第二インデックス格納位置探索ユニット１２３は、レジスタファイル１１０に格納されたインデックスの値に基づいて、第二インデックスをレジスタファイル１１０のどの位置に格納すべきか探索する。【００４４】
第二インデックス格納ユニット１２４は、第二インデックス格納位置探索ユニット１２３が探索した格納位置に基づいて、第二インデックスをレジスタファイル１１０へ格納する。【００４５】
命令デコーダ１３０は命令をデコードするユニットである。命令デコーダ１３０は、非０信号のインデックスを求める命令に応答して、命令語に対応するベースインデックスを第二インデックス計算ユニット１２２へ与え、第一インデックス計算ユニット１２１と第二インデックス計算ユニット１２２と第二インデックス格納位置探索ユニット１２３と第二インデックス格納ユニット１２４とを動作させる。【００４６】
本実施例の動作について説明する。以下では、ランレングス符号化の対象となる信号がＳ個あると仮定する。【００４７】
本実施例においては、ランレングス符号化の対象となるＳ個の信号をＮ個の信号からなる複数の信号グループに分ける。ただしＮ＜＝Ｓとする。もしＳがＮと等しいなら、信号グループの数は一つだけである。【００４８】
Ｎ個の信号に含まれる非０信号のインデックスを求める手順について説明する。この手順をＮ個毎にグループ分けされた全ての信号グループについて繰り返すことによって、Ｓ個の信号に含まれる非０信号のインデックスを求めることができる。【００４９】
初めに、ランレングス符号化の対象となるＳ個の信号から一つの信号グループを取り出す。その信号グループに含まれるＮ個の信号ｓ（ｎ）（ｎ＝０、１、２、．．．、Ｎ−１）をレジスタファイル１１０へ格納する。【００５０】
Ｎ個の信号ｓ（ｎ）の最初の信号ｓ（０）のインデックスをＢとする。Ｂを信号ｓ（ｎ）（ｎ＝０、１、２、．．．、Ｎ−１）のベースインデックスとする。【００５１】
Ｓ個の信号のインデックス０からＢ−１までの信号に対する非０信号のインデックスがレジスタファイル１１０に格納されているものとする。レジスタファイル１１０に格納されている非０信号のインデックスをｘ（ｋ）（ｋ＝０、１、２、．．．、Ｋ−１）と表すことにする。インデックスｘ（ｋ）の個数Ｋは信号の個数Ｎ以上であるとする（Ｎ＜＝Ｋ）。【００５２】
ランレングス符号化では一般に０の信号の出現頻度が高く、非０信号の出現頻度が低い。したがって、信号の総数Ｓよりも非０信号のインデックスの数Ｋは少ないのが一般的である（Ｋ＜Ｓ）。【００５３】
正常な非０信号のインデックスは０以上の値をとる。このことを利用して正常な非０信号のインデックスか否かを判定する。【００５４】
全ての演算を開始する前に、レジスタファイル１１０に格納されているＫ個の非０信号のインデックスｘ（ｋ）（ｋ＝０、１、２、．．．、Ｋ−１）を負の値で初期化しておく。例えばｘ（ｋ）へ−１を代入しておく。【００５５】
信号ｓ（ｎ）（ｎ＝０、１、２、．．．、Ｎ−１）から発見された非０信号のインデックスは以下に説明する操作によってｘ（ｋ）へ格納されていく。【００５６】
Ｓ個の信号に含まれる全ての非０信号のインデックスを発見した後、正常な非０信号のインデックスｘ（ｋ）は０以上の値を、初期化されたままのｘ（ｋ）は負の値をもつ。【００５７】
本実施例のプロセッサは非０信号検出命令という命令をもつ。非０信号検出命令は信号ｓ（ｎ）に含まれる非０信号のインデックスを求めることができる。【００５８】
デコードした命令が非０信号検出命令ならば、命令デコーダ１３０は非０信号検出ユニット１２０を動作させる。なお、本発明においては、非０信号検出ユニット１２０の各ユニット１２１〜１２４の処理をプロセッサ（コンピュータ）のプログラムで実現するようにしてもよい。【００５９】
次に、図２を参照して、非０信号検出ユニット１２０の動作について説明する。非０信号検出ユニット１２０は命令デコーダ１３０から以下の三つの情報を受けとる。【００６０】
（１）信号ｓ（ｎ）のベースインデックスＢ。【００６１】
（２）信号ｓ（ｎ）が格納されているレジスタ番号（図１のレジスタファイル１１０のレジスタの番号）。本実施例では、図２のレジスタ１１１にｓ（ｎ）（ｎ＝０、１、・・・Ｎ−１）が格納されているものとする。【００６２】
（３）非０信号のインデックスｘ（ｋ）が格納されているレジスタ番号（図１のレジスタファイル１１０のレジスタの番号）。本実施例では、図２のレジスタ１１２にｘ（ｋ）（ｋ＝０、１、・・・Ｋ−１）が格納されているとする。【００６３】
非０信号検出ユニット１２０は、レジスタ１１１から信号ｓ（ｎ）（ｎ＝０、１、２、．．．、Ｎ−１）を読み込む。【００６４】
ベースインデックスＢを使って、信号ｓ（ｎ）（ｎ＝０、１、２、．．．、Ｎ−１）のインデックスをＢ＋０、Ｂ＋１、Ｂ＋２、．．．、Ｂ＋Ｎ−１と定義する。【００６５】
非０信号検出ユニット１２０は信号ｓ（ｎ）（ｎ＝０〜Ｎ−１）をスキャンして、非０信号のインデックスを求める。【００６６】
求めた非０信号のインデックスをｐ（ｍ）（ｍ＝０、１、２、．．．、Ｍ−１）とする。ただし、Ｍは信号ｓ（ｎ）（ｎ＝０、１、・・・Ｎ−１）に含まれる非０信号の数とする。【００６７】
さらに、インデックスｐ（ｍ）よりもｐ（ｍ＋１）が等しいか大きいとする（ｐ（ｍ）＜＝ｐ（ｍ＋１））。【００６８】
続いて、非０信号検出ユニット１２０はレジスタ１１２からインデックスｘ（ｋ）（ｋ＝０、１、・・・Ｋ−１）を取り込む。【００６９】
非０信号検出ユニット１２０はｘ（ｋ）（ｋ＝０〜Ｋ−１）をスキャンして、最もｋが小さい負のインデックスｘ（ｋ）をｘ（Ｇ）とする。インデックスｘ（Ｇ）以降のインデックスｘ（ｋ）（ただし、Ｇ＜＝ｋ）は、負の値をもつインデックスなので初期化されたままの状態のインデックスである。【００７０】
もしＫ個のインデックスｘ（ｋ）（ｋ＝０、１、・・・Ｋ−１）のなかに負のインデックスが無いなら、Ｇは未定義の値とする。【００７１】
続いて、非０信号検出ユニット１２０はｘ（ｋ）とｐ（ｍ）とを用いてインデックスｘ（ｋ）（ｋ＝０、１、２、．．．、Ｋ−１）を以下のように更新する。更新後のインデックスをｙ（ｋ）（ｋ＝０、１、２、．．．、Ｋ−１）とする。【００７２】
０＜＝ｋ＜Ｇの場合、        ｙ（ｋ）＝ｘ（ｋ）；
Ｇ＜＝ｋ＜（Ｇ＋Ｍ）の場合、ｙ（ｋ）＝ｐ（ｋ−Ｇ）；  
（Ｇ＋Ｍ）＜＝ｋ＜Ｋの場合、ｙ（ｋ）＝ｘ（ｋ）；
・・・(1)【００７３】
つまり、更新前のインデックスｘ（ｋ）へ信号ｓ（ｎ）に含まれる非０信号のインデックスｐ（ｍ）を追加することによって、更新後のインデックスｙ（ｋ）が得られる。【００７４】
ｙ（ｋ）を正しく計算するためには、Ｇ、Ｋ、Ｍに、
（Ｇ＋Ｍ）＜＝Ｋ                                ・・・(2)
という関係が成り立つことが必要である。【００７５】
本実施例において、非０信号検出ユニット１２０を使用する際には常にこの関係が満たされることが必要である。【００７６】
もし、
Ｋ＜（Ｇ＋Ｍ）                                  ・・・(3)
という関係になる場合には、更新後のインデックスｙ（ｋ）は未定義の値とする。【００７７】
最後に、非０信号検出ユニット１２０は更新後のインデックスｙ（ｋ）（ｋ＝０、１、２、．．．、Ｋ−１）をレジスタ１１２へ書き込む。【００７８】
以上の手順により、一つの信号グループに含まれるＮ個の信号ｓ（ｎ）（ｎ＝０、１、２、．．．、Ｎ−１）の非０信号のインデックスを求めることができる。【００７９】
Ｓ個の信号について非０信号のインデックスを求める手順を以下にまとめる。図４は、本実施例の手順を模式的に示す図である。【００８０】
信号をＮ個ずつＬ組にわける（図４のステップＳ１）。【００８１】
インデックスを初期化するために、レジスタ１１２に−１を格納する（図４のステップＳ２）。レジスタ１１２内容が非０信号のインデックスｘ（ｋ）である。【００８２】
ｉ＝０として（図４のステップＳ４）、Ｌ−１までｉを１ずつ増加させながら（図４のステップＳ７）、ステップＳ５とＳ６の処理を繰り返す。【００８３】
ｉ番目のＮ個の信号の組ｓ（ｎ）（ｎ＝０、１、２、．．．、Ｎ−１）をレジスタ１１１へ格納する（図４のステップＳ５）。【００８４】
ベースインデックスＢをＮ×ｉとして非０信号検出ユニット１２０を動作させ、レジスタ１１１に格納されたＮ個の信号ｓ（ｎ）の非０信号のインデックスを求め、求めたインデックスをレジスタ１１２へ格納する（図４のステップＳ６）。そして、ｉへ１を加算し（図４のステップＳ７）、ｉ＜ＬならステップＳ５へ戻り（図４のステップＳ８のｙｅｓ分岐）、Ｌ＜＝ｉなら処理を終了する（図４のステップＳ８のｎｏ分岐）。【００８５】
レジスタ１１２に負のインデックスがＮ個以上ある場合、上記したステップＳ６においてレジスタ１１２から非０信号のインデックスが溢れることはない。【００８６】
レジスタ１１２に負のインデックスがＮ個以上ない場合、図４のステップＳ６の処理において、レジスタ１１２から非０信号のインデックスが溢れる可能性がある。図４のステップＳ５とステップＳ６の間で、適切な処理を行う必要がある。【００８７】
具体的には、図４のステップＳ５とステップＳ６の間に以下の処理ステップを挿入する。【００８８】
（ａ）レジスタ１１２に格納されているＮ個以上の非負のインデックスをメモリへ退避する。【００８９】
（ｂ）次に、メモリへ格納された非負のインデックスがレジスタからシフトアウトされるように、レジスタ１１２を算術右シフトする。【００９０】
このようにして、非０信号検出ユニット１２０はＳ個の信号の非０信号のインデックスを求めることができる。【００９１】
ただし、非０信号の数がＫを上回ることが予想される場合、レジスタ１１２から非０信号のインデックスが溢れないようにする必要がある。【００９２】
次に、図３を参照して、本実施例の動作ついて具体的に説明する。【００９３】
以下の説明では、レジスタファイル１１０は１６本の６４ビットレジスタをもち、レジスタ１１１とレジスタ１１２はそれぞれ６４ビットのレジスタとする。【００９４】
Ｎ＝４個の信号ｓ（ｎ）（ｎ＝０、１、２、３）に含まれる非０信号のインデックスｘ（ｋ）を求める処理について説明する。ただし、信号ｓ（ｎ）は、１６ビット符号付き整数(16-Bit Signed Integer)、インデックスｘ（ｋ）は８ビット符号付き整数(8-Bit Signed Integer)とする。【００９５】
インデックスを求める前に、インデックスの初期値と信号をレジスタへ格納する。Ｎ＝４個の信号ｓ（ｎ）（ｎ＝０、１、２、３）をレジスタ１１１へ格納する。【００９６】
ｓ（０）＝２４；
ｓ（１）＝０；
ｓ（２）＝０；
ｓ（３）＝８；【００９７】
レジスタ１１１のＬＳＢ（Least Significant Bit）側にｓ（０）が、ＭＳＢ（Most Significant  Bit）側にｓ（３）が格納されるとする。【００９８】
８個の非０信号のインデックスｘ（ｋ）（ｋ＝０、１、２、．．．、７）の初期値を−１とする。このインデックスｘ（ｋ）をレジスタ１１２へ格納する。【００９９】
次に、ベースインデックスＢ＝０として、非０信号検出ユニット１２０を動作させる。【０１００】
すると、非０信号検出ユニット１２０はレジスタ１１１から信号ｓ（ｎ）（ｎ＝０、１、２、３）を、レジスタ１１２から非０信号のインデックスｘ（ｋ）（ｋ＝０、１、２、．．．、７）をそれぞれ読み込む。【０１０１】
非０信号検出ユニット１２０は信号ｓ（ｎ）（ｎ＝０、１、２、３）をスキャンして、非０信号のインデックスｐ（ｍ）（ｍ＝０、１、２、．．．、Ｍ−１）を見つける。【０１０２】
信号ｓ（ｎ）のなかで、非０信号は、ｓ（０）とｓ（３）である。信号ｓ（０）、ｓ（１）、ｓ（２）、ｓ（３）のインデックスは、レジスタ１１１のＬＳＢ側から順にそれぞれ、Ｂ＋０、Ｂ＋１、Ｂ＋２、Ｂ＋３であり、非０信号検出ユニット１２０へ与えられたベースインデックスＢは０であるため、
ｓ（０）のインデックスはｐ（０）＝０;
ｓ（３）のインデックスはｐ（１）＝３;
となる。【０１０３】
次に、非０信号検出ユニット１２０はインデックスｘ（ｋ）をスキャンして、レジスタ１１２のなかで最もＬＳＢ側にある負のインデックスｘ（Ｇ）を見つける。この状態では全てのインデックスｘ（ｋ）が−１であるため、最もＬＳＢ側にある負のインデックスはｘ（Ｇ）＝ｘ（０）である。【０１０４】
次に、非０信号検出ユニット１２０はレジスタ１１２から読み込んだインデックスｘ（ｋ）と信号ｓ（ｎ）から求めたインデックスｐ（ｍ）とを用いて、インデックスｘ（ｋ）を更新する。【０１０５】
レジスタ１１２から読み込んだインデックスｘ（ｋ）において、最もＬＳＢ側にある負のインデックスは、ｘ（Ｇ）＝ｘ（０）であるため、非０信号検出ユニット１２０は更新後のインデックスｙ（ｋ）（ｋ＝０、１、２、．．．、７）を以下のように計算する。【０１０６】
ｙ（０）＝ｐ（０）＝０；
ｙ（１）＝ｐ（１）＝３；
ｙ（２）＝ｘ（２）＝−１；
ｙ（３）＝ｘ（３）＝−１；
ｙ（４）＝ｘ（４）＝−１；
ｙ（５）＝ｘ（５）＝−１；
ｙ（６）＝ｘ（６）＝−１；
ｙ（７）＝ｘ（７）＝−１；【０１０７】
最後に、非０信号検出ユニット１２０は更新後のインデックスｙ（ｋ）（ｋ＝０、１、２、．．．、７）をレジスタ１１２へ書き込む。【０１０８】
以上のようにして、Ｎ＝４個の信号ｓ（ｎ）（ｎ＝０、１、２、３）に含まれる非０信号のインデックスを求めることができた。【０１０９】
前述したように、本実施例は、Ｎ個よりも多い数の信号から非０信号のインデックスを求めることができる。信号の数がＮ個より多い場合には、信号をＮ個ずつＬ組の信号グループに分割して非０信号のインデックスを求める。【０１１０】
例えば、信号の数が２×Ｎ個の場合には、２回に分けて非０信号のインデックスを求める。【０１１１】
以下の実施例では、Ｎ＝４、信号の数をＳ＝８、として非０信号のインデックスを求める手順を説明する。この場合、Ｓ＝Ｌ×Ｎ＝２×４なので、２回に分けて非０信号のインデックスを求める。【０１１２】
以下では、前記実施例１と同じように、レジスタファイル１１０は１６本の６４ビットレジスタをもち、レジスタ１１１とレジスタ１１２はそれぞれ６４ビットのレジスタとする。【０１１３】
さらに、信号ｓ（ｎ）は１６ビット符号付き整数、インデックスｘ（ｋ）は８ビット符号付き整数とする。【０１１４】
８個の信号ｓ（ｎ）（ｎ＝０、１、２、．．．、７）の値を、以下のように定義する。【０１１５】
８個のうち、最初の４個の信号ｓ（ｎ）（ｎ＝０、１、２、３）の値は、前記実施例１と同じである。【０１１６】
ｓ（０）＝２４；
ｓ（１）＝０；
ｓ（２）＝０；
ｓ（３）＝８；
ｓ（４）＝０；
ｓ（５）＝−１１；
ｓ（６）＝０；
ｓ（７）＝０；【０１１７】
レジスタファイル１１０の構成と信号ｓ（ｎ）（ｎ＝０、１、２、３）の値は、前記実施例１と同じである。実施例１と全く同じようにして、信号ｓ（ｎ）（ｎ＝０、１、２、３）の非０信号のインデックスを求めることができる。【０１１８】
そこで、前記実施例１と同じように、レジスタ１１１に、Ｎ＝４個の信号ｓ（ｎ）（ｎ＝０、１、２、３）を、レジスタ１１２に非０信号のインデックスの初期値を、それぞれ格納してベースインデックスＢ＝０として、非０信号検出ユニット１２０を動作させれば、レジスタ１１２に、以下の非０信号のインデックスが求まる。これは、前記実施例１と同じ結果である。【０１１９】
ｙ（０）＝０；
ｙ（１）＝３；
ｙ（２）＝−１；
ｙ（３）＝−１；
ｙ（４）＝−１；
ｙ（５）＝−１；
ｙ（６）＝−１；
ｙ（７）＝−１；【０１２０】
次に、もう一組の、Ｎ＝４個の信号ｓ（ｎ）（ｎ＝４、５、６、７）に含まれる非０信号のインデックスを求める。【０１２１】
レジスタ１１１に信号ｓ（ｎ）（ｎ＝４、５、６、７）を格納し、レジスタ１１２のインデックスｙ（ｋ）（ｋ＝０、１、２、．．．、７）を新たなインデックスｘ（ｋ）（ｋ＝０、１、２、．．．、７）とみなして、ベースインデックスＢ＝４として、非０信号検出ユニット１２０を動作させる。【０１２２】
非０信号検出ユニット１２０はレジスタ１１１から信号ｓ（ｎ）（ｎ＝４、５、６、７）を、レジスタ１１２から非０信号のインデックスｘ（ｋ）（ｋ＝０、１、２、．．．、７）をそれぞれ読み込む。【０１２３】
非０信号検出ユニット１２０は信号ｓ（ｎ）をスキャンして、非０信号のインデックスｐ（ｍ）（ただし、ｍ＝０、１、２、．．．、Ｍ−１）を見つける。【０１２４】
信号ｓ（ｎ）のなかで非０信号はｓ（５）だけである。【０１２５】
信号ｓ（ｎ）のインデックスはレジスタ１１１のＬＳＢ側から順にそれぞれ、Ｂ＋０、Ｂ＋１、Ｂ＋２、Ｂ＋３であり、非０信号検出ユニット１２０へ与えられたベースインデックスＢは４であるため、ｓ（５）のインデックスはｐ（０）＝５となる。【０１２６】
次に、非０信号検出ユニット１２０はインデックスｘ（ｋ）をスキャンして、レジスタ１１２のなかで最もＬＳＢ側にある負のインデックスｘ（Ｇ）を見つける。【０１２７】
この状態ではインデックスの値は、
ｘ（０）＝０；
ｘ（１）＝３；
ｘ（２）＝−１；
ｘ（３）＝−１；
．．．；
である。【０１２８】
したがって、最もＬＳＢ側にある負のインデックスは、
ｘ（Ｇ）＝ｘ（２）
である。【０１２９】
次に、非０信号検出ユニット１２０はレジスタ１１２から読み込んだインデックスｘ（ｋ）と信号ｓ（ｎ）から求めたインデックスｐ（ｍ）とを使ってインデックスｘ（ｋ）を更新する。【０１３０】
レジスタ１１２から読み込んだインデックスｘ（ｋ）において、最もＬＳＢ側にある負のインデックスは、
ｘ（Ｇ）＝ｘ（２）
であるため、非０信号検出ユニット１２０は更新後のインデックスｙ（ｋ）（ｋ＝０、１、２、．．．、７）を以下のように計算する。【０１３１】
ｙ（０）＝ｘ（０）＝０；
ｙ（１）＝ｘ（１）＝３；
ｙ（２）＝ｐ（２）＝５；
ｙ（３）＝ｘ（３）＝−１；
ｙ（４）＝ｘ（４）＝−１；
ｙ（５）＝ｘ（５）＝−１；
ｙ（６）＝ｘ（６）＝−１；
ｙ（７）＝ｘ（７）＝−１；【０１３２】
最後に、非０信号検出ユニット１２０は更新後のインデックスｙ（ｋ）（ｋ＝０、１、２、．．．、７）をレジスタ１１２へ書き込む。【０１３３】
以上のようにして、８個の信号ｓ（ｎ）（ｎ＝０、１、２、．．．、７）に含まれる非０信号のインデックスを求めることができる。【０１３４】
同様にして、１２個や１６個あるいはそれ以上の信号についても非０信号のインデックスを求めることができる。【０１３５】
次に、非０信号のインデックスを使ったランレングスの求め方について説明する。【０１３６】
非０信号の前に出現する０の数（ランレングス）を非０信号のインデックスから計算することができる。その計算方法について以下に説明する。【０１３７】
上記した手法を使って、Ｎ個の信号ｓ（ｎ）（ｎ＝０、１、２、．．．、Ｎ−１）について、非０信号のインデックスｘ（ｋ）（ｋ＝０、１、２、．．．、Ｋ−１）が求められたものと仮定する。ただし、正常なインデックスｘ（ｋ）は０以上で、負のｘ（ｋ）はインデックスではないと仮定する。【０１３８】
さらに、正常なインデックス０＜＝ｘ（ｋ）について、
ｘ（ｋ）＜＝ｘ（ｋ＋１）                ・・・(4)
という関係が成り立つものと仮定する。【０１３９】
さらに、正常なインデックス以外の全てのインデックスは−Ｎという負の値をもつと仮定する。【０１４０】
前記した実施例ではｘ（ｋ）の初期値を−１としていたが、ｘ（ｋ）の初期値は負の値ならどんな値でも良い。ここでは、ランレングスを求めるためにｘ（ｋ）の初期値を−Ｎとする。【０１４１】
非０信号のインデックスｘ（ｋ）から、ランレングスｚ（ｋ）を以下のようにして計算する。【０１４２】
ｘ（ｋ）をａ（ｋ）へ代入する。
ａ（ｋ）＝ｘ（ｋ）                          ・・・(5)【０１４３】
次に、ａ（ｋ）の各要素を一つ番号が大きい方向へずらす。すなわち、
ａ（ｋ−１）＝ａ（ｋ−２）；
ａ（ｋ−２）＝ａ（ｋ−３）；
．．．
ａ（３）＝ａ（２）；
ａ（２）＝ａ（１）；
ａ（１）＝ａ（０）；
・・・(6)
という具合にａ（ｋ）の値をずらす。そしてａ（０）へ０を代入する。【０１４４】
次に、ｘ（ｋ）の各要素とａ（ｋ）の対応する要素との差をｂ（ｋ）とする。すなわち、
ｂ（ｋ）＝ｘ（ｋ）−ａ（ｋ）                      ・・・(7)
（ｋ＝０、１、２、．．．、Ｋ−１）
とする。【０１４５】
次に、ｂ（ｋ）の各要素と２×Ｎとの和をｃ（ｋ）とする。すなわち、
ｃ（ｋ）＝ｂ（ｋ）＋２×Ｎ                          ・・・(8)
（ｋ＝０、１、２、．．．、Ｋ−１）
とする。【０１４６】
次に、ｃ（ｋ）の各要素の下位ｌｏｇ２（Ｎ）ビットだけを抽出し、それをｄ（ｋ）とする。すなわち、
ｄ（ｋ）＝ｃ（ｋ）＆（（１＜＜ｌｏｇ２（Ｎ））−１）              ・・・(9)
（ｋ＝０、１、２、．．．、Ｋ−１）
とする。【０１４７】
式（９）において、＆はアンド（ＡＮＤ）演算子である。＜＜は左シフト（Ｓｈｉｆｔ）演算子であり、ａ＜＜ｂはａをｂビット左シフトする。例えばＮ＝１６の場合、ｌｏｇ２（１６）は４となり、０ｘ１（ｘはヘキサデシマル表示）を４ビット左シフトしたものから１を減算すると０ｘＦとなる。よって、Ｎ＝１６ならば、ｃ（ｋ）の下位４ビットを抽出した値がｄ（ｋ）となる。【０１４８】
次に、ｄ（ｋ）の各要素と１との差をｅ（ｋ）とする。すなわち、
ｅ（ｋ）＝ｄ（ｋ）−１                            ・・・(10)
（ｋ＝０、１、２、．．．、Ｋ−１）
とする。【０１４９】
次に、ｅ（ｋ）をｚ（ｋ）へ代入する。
ｚ（ｋ）＝ｅ（ｋ）                                ・・・(11)【０１５０】
そして、ｚ（ｋ）の各要素を一つ番号が小さい方向へずらす。すなわち、
ｚ（０）＝ｚ（１）；
ｚ（１）＝ｚ（２）；
ｚ（２）＝ｚ（３）；
…
ｚ（ｋ−１）＝ｚ（ｋ−２）；
・・・(12)
という具合にｚ（ｋ）の値をずらす。【０１５１】
そして、ｚ（１５）へ−１を代入する。【０１５２】
このｚ（ｋ）がインデックスｘ（ｋ）に対応するランレングスである。【０１５３】
図６は１６個の信号ｓ（ｎ）（ｎ＝０、１、２、…、１５）のランレングスｚ（ｋ）を求める例を模式的に示す図である。【０１５４】
図６において、非０信号は、ｓ（０）、ｓ（１）、ｓ（２）、ｓ（５）、ｓ（６）、ｓ（９）、ｓ（１１）である。【０１５５】
信号ｓ（ｎ）の非ゼロ信号インデックスｘ（ｋ）が求められたものと仮定して、図６にもとづいて、ｘ（ｋ）からランレングスｚ（ｋ）を求める具体的手順を述べる。【０１５６】
まず、前述したように、図６の信号ｓ（ｎ）から非０信号のインデックスｘ（ｋ）を求める。【０１５７】
ただし、ｘ（ｋ）の初期値を、
ｘ（ｋ）＝−Ｎ＝−１６  
（ｋ＝０、１、２、．．．、Ｋ−１）
とする。図６（Ａ）には７個の非０信号が存在する。【０１５８】
したがって、非０信号のインデックスｘ（ｋ）の値は、
ｘ（０）＝０；
ｘ（１）＝１；
ｘ（２）＝２；
ｘ（３）＝５；
ｘ（４）＝６；
ｘ（５）＝９；
ｘ（６）＝１１；
ｘ（７）＝−１６；
．．．
のように求まる（図６（Ｂ）参照）。【０１５９】
次に、ｘ（ｋ）からａ（ｋ）を求める。【０１６０】
要素番号ｋが大きくなる方向へｘ（ｋ）を１要素分ずらすとａ（ｋ）が得られる。【０１６１】
したがって、ａ（ｋ）の値は、
ａ（０）＝０；
ａ（１）＝０；
ａ（２）＝１；
ａ（３）＝２；
ａ（４）＝５；
ａ（５）＝６；
ａ（６）＝９；
ａ（７）＝１１；
ａ（８）＝−１６；
．．．；
となる（図６（Ｃ）参照）。【０１６２】
次に、ｘ（ｋ）とａ（ｋ）からｂ（ｋ）を求める。【０１６３】
ｂ（ｋ）＝ｘ（ｋ）−ａ（ｋ）
であるからｂ（ｋ）の値は、
ｂ（０）＝０；
ｂ（１）＝１；
ｂ（２）＝１；
ｂ（３）＝３；
ｂ（４）＝１；
ｂ（５）＝３；
ｂ（６）＝２；
ｂ（７）＝−２７；
ｂ（８）＝０；
．．．；
となる（図６（Ｄ）参照）。【０１６４】
次に、ｂ（ｋ）からｃ（ｋ）を求める。【０１６５】
ｃ（ｋ）＝ｂ（ｋ）＋２Ｎ
＝ｂ（ｋ）＋３２
であるからｃ（ｋ）の値は、
ｃ（０）＝３２；
ｃ（１）＝３３；
ｃ（２）＝３３；
ｃ（３）＝３５；
ｃ（４）＝３３；
ｃ（５）＝３５；
ｃ（６）＝３４；
ｃ（７）＝３５；
ｃ（８）＝３２；
．．．；
となる（図６（Ｅ）参照）。【０１６６】
次に、ｃ（ｋ）からｄ（ｋ）を求める。【０１６７】
ｄ（ｋ）＝ｃ（ｋ）＆０ｘＦであるから、ｄ（ｋ）の値は、
ｄ（０）＝０；
ｄ（１）＝１；
ｄ（２）＝１；
ｄ（３）＝３；
ｄ（４）＝１；
ｄ（５）＝３；
ｄ（６）＝２；
ｄ（７）＝５；
ｄ（８）＝０；
．．．；
となる（図６（Ｆ）参照）。【０１６８】
次に、ｄ（ｋ）からｅ（ｋ）を求める。【０１６９】
ｅ（ｋ）＝ｄ（ｋ）−１であるから、ｅ（ｋ）の値は、
ｅ（０）＝−１；
ｅ（１）＝０；
ｅ（２）＝０；
ｅ（３）＝２；
ｅ（４）＝０；
ｅ（５）＝２；
ｅ（６）＝１；
ｅ（７）＝４；
ｅ（８）＝−１；
．．．；
となる（図６（Ｇ）参照）。【０１７０】
最後に、ｅ（ｋ）からランレングスｚ（ｋ）を求める。【０１７１】
要素番号ｋが小さくなる方向へｅ（ｋ）を１要素分ずらすとｚ（ｋ）が得られる。【０１７２】
したがって、ｚ（ｋ）の値は、
ｚ（０）＝０；
ｚ（１）＝０；
ｚ（２）＝２；
ｚ（３）＝０；
ｚ（４）＝２；
ｚ（５）＝１；
ｚ（６）＝４；
ｚ（７）＝−１；
である（図６（Ｈ）参照）。【０１７３】
ｚ（ｋ）が非０信号のインデックスｘ（ｋ）の各要素に対応するランレングスである。【０１７４】
次に本実施例の応用について述べる。【０１７５】
プロセッサは前記実施例に限定されることなく、さまざまに応用可能である。以下では具体的にどのような部分を応用可能であるかについて述べる。【０１７６】
本実施例のプロセッサのレジスタファイル１１０は６４ビットのレジスタを１６本もつ。【０１７７】
この構成は一つの例であり、非０信号検出ユニット１２０が動作する範囲で変更可能である。【０１７８】
例えば、１６ビットレジスタ３２本、３２ビットレジスタ１６本、３２ビットレジスタ３２本、３２ビットレジスタ６４本、６４ビットレジスタ６４本、１２８ビットレジスタ８本、１２８ビットレジスタ１６本、１２８ビットレジスタ３２本、などの構成が考えられる。【０１７９】
本実施例の非０信号検出ユニット１２０はレジスタ１１１から信号を、レジスタ１１２からインデックスを、それぞれ読み込んでインデックスを更新する。そして、更新したインデックスを再びレジスタ１１２へ書き込む。【０１８０】
これは一つの例であり、非０信号検出ユニット１２０は更新前のインデックスが格納されたレジスタとは別のレジスタへ更新後のインデックスを書き込むことも可能である。【０１８１】
本実施例の非０信号検出ユニット１２０はレジスタ１１１とレジスタ１１２を使用するが、非０信号検出ユニット１２０が使用するレジスタを別のレジスタへ変更することも可能である。【０１８２】
例えば、命令語の中に非０信号検出ユニット１２０が使用するレジスタを記述しておけば、命令によって非０信号検出ユニット１２０が使用するレジスタを変更することができる。【０１８３】
本実施例の非０信号検出ユニット１２０はレジスタ１１１から信号を読み込むが、複数のレジスタから信号を読み込むようにすることも可能である。【０１８４】
例えば、Ｎ個の信号をいくつかのレジスタに分割して格納しておいて、非０信号検出ユニット１２０がそれらのレジスタから信号を読み込むようにすることができる。【０１８５】
本実施例の非０信号検出ユニット１２０はレジスタ１１２からインデックスを読み込むが、複数のレジスタからインデックスを読み込むようにすることも可能である。【０１８６】
例えば、Ｋ個のインデックスをいくつかのレジスタに分割して格納しておいて、非０信号検出ユニット１２０がそれらのレジスタからインデックスを読み込むようにすることができる。同じように、実施例の非０信号検出ユニット１２０は更新したインデックスをレジスタ１１２へ書き込むが、複数のレジスタへインデックスを書き込むようにすることも可能である。【０１８７】
本発明はランレングス符号化を使って情報を符号化する任意の装置に適用できる。例えば、本発明を適用した符号化器を使って画像や音楽を符号化することができる。【０１８８】
以上、本発明を上記実施例に即して説明したが、本発明は上記実施例の構成にのみ制限されるものでなく、本発明の範囲内で当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【図１】
2008066050.tif 000003
【図２】
2008066050.tif 000004
【図３】
2008066050.tif 000005
【図４】
2008066050.tif 000006
【図５】
2008066050.tif 000007
【図６】
2008066050.tif 000008
【国際調査報告】
2008066050.tif 000009
2008066050.tif 000010