(57)【要約】圧縮されたカノニカル・ハフマン符号化データの並列圧縮解除のための装置および方法である。
2004528771.tif 000002
【特許請求の範囲】
【請求項１】
カノニカル・ハフマン符号化データのための圧縮解除デバイスであって、
複数のＦＩＲＳＴＣＯＤＥデータ値を格納するための第１のデータレジスタ手段と、
複数のＳＹＭＢＯＬ  ＰＯＩＮＴＥＲデータ値を格納するための第２のデータレジスタ手段と、
異なるＦＩＲＳＴＣＯＤＥデータ値を、圧縮されたデータのストリングの対応するビットと比較するために結合された比較手段と、
圧縮されたデータのビットを、比較手段の出力に応じて選択されたＦＩＲＳＴＣＯＤＥデータ値の１つおよびＳＹＭＢＯＬ  ＰＯＩＮＴＥＲデータ値の１つと結合し、アドレスを出力する手段と、
アドレスを受信し、対応するシンボルを出力するために結合されたシンボルテーブル手段とを含むデバイス。
【請求項２】
前記結合する手段は、圧縮されたデータのビットおよび関連付けられたＦＩＲＳＴＣＯＤＥデータ値を、関連付けられたＳＹＭＢＯＬ  ＰＯＩＮＴＥＲデータ値により加算かつ減算する手段をさらに含む、請求項１に記載のデバイス。
【請求項３】
結合する手段は、
選択されたＳＹＭＢＯＬ  ＰＯＩＮＴＥＲデータ値を、圧縮されたデータビットのストリングに加算するための加算手段と、
選択されたＦＩＲＳＴＣＯＤＥデータ値を、加算手段の結果から減算するための減算手段とをさらに含む、請求項１に記載のデバイス。
【請求項４】
結合する手段は、
選択されたＦＩＲＳＴＣＯＤＥデータ値を、圧縮されたデータビットのストリングから減算するための減算手段と、
減算手段の結果を、選択されたＳＹＭＢＯＬ  ＰＯＩＮＴＥＲデータ値に加算するための加算手段とをさらに含む、請求項１に記載のデバイス。
【請求項５】
結合する手段によって出力されたアドレスは、異なるＦＩＲＳＴＣＯＤＥデータ値の、圧縮されたデータのストリングの対応するビットとの成功した比較に関連付けられたアドレスをさらに含む、請求項１に記載のデバイス。
【請求項６】
ＦＩＲＳＴＣＯＤＥデータ値の１つおよびＳＹＭＢＯＬ  ＰＯＩＮＴＥＲデータ値の１つを、ＦＩＲＳＴＣＯＤＥデータ値の１つの、圧縮されたデータの関連付けられたビットとの成功した比較に応じて選択する手段をさらに含む、請求項１に記載のデバイス。
【請求項７】
ＦＩＲＳＴＣＯＤＥデータ値の１つの、圧縮されたデータの関連付けられたビットとの成功した比較を決定する手段をさらに含む、請求項６に記載のデバイス。
【請求項８】
比較する手段は、複数のＦＩＲＳＴＣＯＤＥデータ値を、圧縮されたデータの対応する複数のビットと同時に比較する手段をさらに含む、請求項１に記載のデバイス。
【請求項９】
比較する手段は、成功した比較を決定するために複数の比較結果を順次検査する手段をさらに含む、請求項１に記載のデバイス。
【請求項１０】
シンボルテーブル手段による、受信されたアドレスに対応するシンボルの出力をレポートする手段をさらに含む、請求項１に記載のデバイス。
【請求項１１】
圧縮されたカノニカル・ハフマン符号化データファイルを格納するためのメモリ手段と、
論理デバイスを動作する手段とをさらに含み、
圧縮解除デバイスが、複数のＦＩＲＳＴＣＯＤＥおよびＳＹＭＢＯＬ  ＰＯＩＮＴＥＲデータ値を受信し、圧縮されたデータを圧縮解除し、解決されたシンボルを出力するためにメモリ手段に結合される、請求項１に記載のデバイス。
【請求項１２】
データファイルにおいてカノニカル・ハフマン符号化データとして圧縮されたデータビットのストリングを圧縮解除するための圧縮解除デバイスであって、データファイルは（ｉ）圧縮されたデータビットのストリング、（ｉｉ）ＦＩＲＳＴＣＯＤＥデータテーブル、（ｉｉｉ）ＳＹＭＢＯＬ  ＰＯＩＮＴＥＲデータテーブル、および（ｉｖ）ＳＹＭＢＯＬテーブルを含み、ＦＩＲＳＴＣＯＤＥデータテーブルにおけるデータと圧縮されたデータビットの間で関係が固定され、ＦＩＲＳＴＣＯＤＥデータテーブルにおけるデータとＳＹＭＢＯＬ  ＰＯＩＮＴＥＲデータテーブルにおけるデータの間で関係が固定され、
（ａ）カノニカル・ハフマン符号化データファイルを受信するために構成された結合と、
（ｂ）データファイルのＦＩＲＳＴＣＯＤＥデータテーブル部からデータ値を受信かつ格納するように結合された、複数のＦＩＲＳＴＣＯＤＥデータレジスタと、
（ｃ）データファイルのＳＹＭＢＯＬ  ＰＯＩＮＴＥＲデータテーブル部からデータ値を受信かつ格納するように結合された、複数のＳＹＭＢＯＬ  ＰＯＩＮＴＥＲデータレジスタと、
（ｄ）各ＦＩＲＳＴＣＯＤＥデータレジスタに格納された値を、圧縮されたデータビットのストリングの対応するビットと比較するための、各ＦＩＲＳＴＣＯＤＥレジスタと圧縮されたデータビットのストリングの間に結合された比較器と、
（ｅ）成功した比較結果を決定し、それに応答して、それに関連付けられた解決されたシンボルアドレスを出力するための、各比較器に結合されたマルチプレクサと、
（ｆ）マルチプレクサ、および、各ＳＹＭＢＯＬ  ＰＯＩＮＴＥＲデータレジスタおよび対応するＦＩＲＳＴＣＯＤＥデータレジスタに結合された中間結合加算および減算ブロックであって、
（ｉ）成功した比較結果に関連付けられた、ＳＹＭＢＯＬ  ＰＯＩＮＴＥＲデータレジスタに格納された値を、圧縮されたデータビットのストリングの対応するビットに加算すること、
（ｉｉ）成功した比較に関連付けられた、ＦＩＲＳＴＣＯＤＥデータレジスタに格納された値を、圧縮されたデータビットのストリングの対応するビットから減算すること、
（ｉｉｉ）解決されたシンボルアドレスを生成すること、および
（ｉｖ）応答して、対応する解決されたシンボルを出力するために、解決されたシンボルアドレスをデータファイルのＳＹＭＢＯＬテーブル部に出力することを行うための中間結合加算および減算ブロックとを含むデバイス。
【請求項１３】
中間結合加算および減算ブロックはマルチプレクサからの入力に応答して動作する、請求項１２に記載のデバイス。
【請求項１４】
中間結合加算および減算ブロックは、第１の構成および第２の構成のうち１つによって、解決されたシンボルアドレスを生成するために動作可能であり、
第１の構成によれば、
成功した比較に関連付けられた、ＳＹＭＢＯＬ  ＰＯＩＮＴＥＲデータレジスタに格納された値を、圧縮されたデータビットのストリングの対応するビットに加算するために、加算ブロックの１つが各ＳＹＭＢＯＬ  ＰＯＩＮＴＥＲデータレジスタに結合され、
減算ブロックの１つが各加算ブロックおよび対応するＦＩＲＳＴＣＯＤＥレジスタに結合され、マルチプレクサからの入力に応答して、解決されたシンボルアドレスを生成するために、成功した比較に関連付けられた、ＦＩＲＳＴＣＯＤＥデータレジスタに格納された値を、関連付けられた加算ブロックの結果から減算するように動作可能であり、
第２の構成によれば、
マルチプレクサからの入力に応答して、成功した比較に関連付けられた、ＦＩＲＳＴＣＯＤＥデータレジスタに格納された値を、圧縮されたデータビットのストリングから減算するために、減算ブロックの１つが各ＦＩＲＳＴＣＯＤＥデータレジスタに結合され、
解決されたシンボルアドレスを生成するために、成功した比較に関連付けられた、ＳＹＭＢＯＬ  ＰＯＩＮＴＥＲデータレジスタに格納された値を、関連付けられた減算ブロックの結果に加算するために、加算ブロックの１つが各ＳＹＭＢＯＬ  ＰＯＩＮＴＥＲデータレジスタに結合される、請求項１２に記載のデバイス。
【請求項１５】
データファイルにおいてカノニカル・ハフマン符号化データとして圧縮されたデータビットのストリングをその中に格納しているメモリデバイスと、
メモリデバイスに結合され、論理デバイスを動作するプロセッサとをさらに含み、
圧縮解除デバイスの結合が、それぞれデータファイルを受信するため、かつ解決されたシンボルを出力するためにさらにメモリに結合される、請求項１２に記載のデバイス。
【請求項１６】
圧縮解除デバイスは、プロセッサからの命令を受信するための結合をさらに含む、請求項１５に記載のデバイス。
【請求項１７】
カノニカル・ハフマン符号化データファイルにおいて圧縮されたデータの圧縮解除のためのデバイスであって、データファイルは、圧縮されたデータビットのストリング、ＦＩＲＳＴＣＯＤＥデータテーブル、ＳＹＭＢＯＬ  ＰＯＩＮＴＥＲデータテーブル、およびＳＹＭＢＯＬテーブルを含み、ＦＩＲＳＴＣＯＤＥと圧縮されたデータビットの間で関係が、ＦＩＲＳＴＣＯＤＥ［０］およびビット０、ＦＩＲＳＴＣＯＤＥ［１］およびビット０、１、ＦＩＲＳＴＣＯＤＥ［２］およびビット０、１、２、からＦＩＲＳＴＣＯＤＥ［Ｎ］およびビット０、１、２、．．．Ｎに従って固定され、ＦＩＲＳＴＣＯＤＥとＳＹＭＢＯＬ  ＰＯＩＮＴＥＲの間で関係が、ＦＩＲＳＴＣＯＤＥ［０］およびＳＹＭＢＯＬ  ＰＯＩＮＴＥＲ［０］、ＦＩＲＳＴＣＯＤＥ［１］およびＳＹＭＢＯＬ  ＰＯＩＮＴＥＲ［１］、からＦＩＲＳＴＣＯＤＥ［Ｎ］およびＳＹＭＢＯＬ  ＰＯＩＮＴＥＲ［Ｎ］に従って固定され、
各々がそれに関連付けられたＦＩＲＳＴＣＯＤＥ値を有する複数のＦＩＲＳＴＣＯＤＥレジスタと、
各々がそれに関連付けられたＳＹＭＢＯＬ  ＰＯＩＮＴＥＲ値を有する複数のＳＹＭＢＯＬ  ＰＯＩＮＴＥＲと、
各々が、そこからＦＩＲＳＴＣＯＤＥ値を受け入れるように異なるＦＩＲＳＴＣＯＤＥレジスタに結合され、その中に格納された圧縮されたカノニカル・ハフマン符号化データを有するメモリから、圧縮されたデータビットのストリングを受け入れるように結合された、複数の比較器であって、複数のＦＩＲＳＴＣＯＤＥ値を、圧縮されたデータビットのストリングの対応するビットと同時に比較するように構成される比較器と、
各比較器の結果を受け入れるように結合されたマルチプレクサであって、結果を順次検査するように、かつ成功した比較結果を選択するように構成されるマルチプレクサと、
各々が、マルチプレクサの出力、およびＳＹＭＢＯＬ  ＰＯＩＮＴＥＲレジスタのうち異なる１つに結合された複数の加算ブロックであって、加算ブロックの１つは、ＦＩＲＳＴＣＯＤＥレジスタのうち成功した比較結果を有する１つに対応するＳＹＭＢＯＬ  ＰＯＩＮＴＥＲレジスタの１つに関連付けられ、対応するＳＹＭＢＯＬ  ＰＯＩＮＴＥＲレジスタからの値を、圧縮されたデータビットのストリングに加算するように構成される加算ブロックと、
各々がＦＩＲＳＴＣＯＤＥレジスタのうち異なる１つに、かつＦＩＲＳＴＣＯＤＥレジスタのうち１つに対応する加算ブロックの１つに結合された、複数の減算ブロックであって、減算ブロックの１つは、成功した比較結果を有するＦＩＲＳＴＣＯＤＥレジスタに関連付けられ、成功したＦＩＲＳＴＣＯＤＥレジスタの値を対応する加算ブロックの結果から減算するように、かつアドレスをマルチプレクサに出力するように構成される減算ブロックと、
アドレスを受信するようにマルチプレクサに結合されたＳＹＭＢＯＬテーブルであって、受信されたアドレスに関連付けられた解決されたシンボルを出力するように構成されるＳＹＭＢＯＬテーブルとを含むデバイス。
【請求項１８】
カノニカル・ハフマン符号化データファイルを含むメモリをさらに含み、このメモリは、それに関連付けられたＦＩＲＳＴＣＯＤＥ値を出力するために複数の各ＦＩＲＳＴＣＯＤＥレジスタに結合され、それに関連付けられたＳＹＭＢＯＬ  ＰＯＩＮＴＥＲ値を出力するために複数の各ＳＹＭＢＯＬ  ＰＯＩＮＴＥＲレジスタに結合され、アドレスを受信するようにマルチプレクサに結合され、それに応答して、受信されたアドレスに関連付けられた解決されたシンボルを出力するように構成される、請求項１７に記載のデバイス。
【請求項１９】
マルチプレクサからの入力に応答して、成功したＦＩＲＳＴＣＯＤＥレジスタの値を、圧縮されたデータビットのストリングから減算するために、複数の各減算ブロックがＦＩＲＳＴＣＯＤＥレジスタの異なる１つに結合され、
複数の各加算ブロックがそれぞれマルチプレクサの出力、およびＳＹＭＢＯＬ  ＰＯＩＮＴＥＲレジスタのうち異なる１つに結合され、加算ブロックの１つは、成功したＦＩＲＳＴＣＯＤＥレジスタに対応するＳＹＭＢＯＬ  ＰＯＩＮＴＥＲレジスタの１つに関連付けられ、対応するＳＹＭＢＯＬ  ＰＯＩＮＴＥＲレジスタからの値を、対応する加算ブロックの結果に加算するように、かつアドレスをマルチプレクサに出力するように構成される、請求項１７に記載のデバイス。
【請求項２０】
カノニカル・ハフマン符号化データの圧縮解除のための方法であって、
カノニカル・ハフマン符号化データのファイルを受信するステップであって、ファイルは、圧縮されたカノニカル・ハフマン符号化データビットのストリング、ＦＩＲＳＴＣＯＤＥデータ値のテーブル、ＳＹＭＢＯＬ  ＰＯＩＮＴＥＲデータ値のテーブル、および解決されたシンボルのテーブルを含み、
ＦＩＲＳＴＣＯＤＥデータ値をＦＩＲＳＴＣＯＤＥデータレジスタに格納するステップと、
ＳＹＭＢＯＬ  ＰＯＩＮＴＥＲデータ値をＳＹＭＢＯＬ  ＰＯＩＮＴＥＲデータレジスタに格納するステップと、
ＦＩＲＳＴＣＯＤＥデータ値を、圧縮されたデータの対応するビットと比較するステップと、
ＦＩＲＳＴＣＯＤＥデータ値を、圧縮されたデータの対応するビットと比較した結果を検査して、合致を決定するステップと、
圧縮されたデータのビットを、合致の決定に応じて選択されたＦＩＲＳＴＣＯＤＥデータ値の１つおよびＳＹＭＢＯＬ  ＰＯＩＮＴＥＲデータ値の１つと結合するステップと、
アドレスを生成するステップと、
解決されたシンボルのテーブルから、生成されたアドレスに対応するシンボルを出力するステップとを含む方法。
【請求項２１】
圧縮されたデータのビットを、ＦＩＲＳＴＣＯＤＥデータ値の１つおよびＳＹＭＢＯＬ  ＰＯＩＮＴＥＲデータ値の１つと結合するステップは、圧縮されたデータのビットおよび関連付けられたＦＩＲＳＴＣＯＤＥデータ値を、関連付けられたＳＹＭＢＯＬ  ＰＯＩＮＴＥＲデータ値により加算かつ減算するステップをさらに含む、請求項２０に記載の方法。
【請求項２２】
圧縮されたデータのビットを、ＦＩＲＳＴＣＯＤＥデータ値の１つおよびＳＹＭＢＯＬ  ＰＯＩＮＴＥＲデータ値の１つと結合するステップは、
圧縮されたデータビットのストリングに、ＦＩＲＳＴＣＯＤＥデータ値を圧縮されたデータの対応するビットと比較した成功の結果に関連付けられた、ＳＹＭＢＯＬ  ＰＯＩＮＴＥＲデータ値を加算するステップと、
ＦＩＲＳＴＣＯＤＥデータ値を加算の結果から減算するステップとをさらに含む、請求項２０に記載の方法。
【請求項２３】
アドレスを生成するステップは、ＦＩＲＳＴＣＯＤＥデータ値を加算の結果から減算することに応じてアドレスを生成するステップをさらに含む、請求項２２に記載の方法。
【請求項２４】
圧縮されたデータのビットを、ＦＩＲＳＴＣＯＤＥデータ値の１つおよびＳＹＭＢＯＬ  ＰＯＩＮＴＥＲデータ値の１つと結合するステップは、
ＦＩＲＳＴＣＯＤＥデータ値を、圧縮されたデータビットのストリングから減算するステップと、
ＦＩＲＳＴＣＯＤＥデータ値を比較した成功の結果に関連付けられたＳＹＭＢＯＬ  ＰＯＩＮＴＥＲデータ値を、減算の結果に加算するステップとをさらに含む、請求項２０に記載の方法。
【請求項２５】
アドレスを生成するステップは、ＳＹＭＢＯＬ  ＰＯＩＮＴＥＲデータ値を減算の結果に加算することに応じてアドレスを生成するステップをさらに含む、請求項２４に記載の方法。
【請求項２６】
アドレスを生成するステップは、圧縮されたデータのビットをＦＩＲＳＴＣＯＤＥデータ値の１つおよびＳＹＭＢＯＬ  ＰＯＩＮＴＥＲデータ値の１つと結合することに応じて、アドレスを生成するステップをさらに含む、請求項２０に記載の方法。
【請求項２７】
ＦＩＲＳＴＣＯＤＥデータ値を、圧縮されたデータの対応するビットと比較するステップは、２つ以上のＦＩＲＳＴＣＯＤＥデータ値を、圧縮されたデータの対応するビットと同時に比較するステップをさらに含む、請求項２０に記載の方法。
【請求項２８】
ＦＩＲＳＴＣＯＤＥデータ値を、圧縮されたデータの対応するビットと比較した結果を検査するステップは、ＦＩＲＳＴＣＯＤＥデータ値の１つと圧縮されたデータのビットのうち対応する１つの間の合致についての複数の比較結果を順次検査するステップをさらに含む、請求項２０に記載の方法。
【請求項２９】
プロセッサからの命令を受信して、データビットのストリングを、圧縮されたカノニカル・ハフマン符号化データとして圧縮解除するステップと、
カノニカル・ハフマン符号化データのファイルを、プロセッサに関連付けられたメモリから受信するステップと、
圧縮解除のための方法を、命令に応答して動作するステップとをさらに含む、請求項２０に記載の方法。
【請求項３０】
解決されたシンボルをメモリに出力するステップをさらに含む、請求項２９に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデジタル信号処理に関し、より詳細にはデジタル信号圧縮解除に関する。
【背景技術】
【０００２】
近年の高速コンピュータの発達により、大容量のデータがコンピュータ内で処理されるようになってきた。通常、データが圧縮されて、使用可能メモリが効率的に使用され、データ伝送回数が減らされる。様々なデータ圧縮方法が知られている。１つの圧縮方法はハフマン符号化として知られ、各データ文字の確率が１連のビットに変換される統計的符号化の形式である。
【０００３】
従来のハフマン符号化は各シンボルについて最適なプレフィックスなしのコードを、各シンボルがファイル内で現れる頻度に基づいて割り当てる。より頻繁に現れるシンボルが、より少数のビットにおいて符号化される。標準のハフマン符号化では、これが、バイナリツリー構造を構築することによって実施される。次いで、このツリー構造が使用されて、コードワードが構築される。コードワードの復号化には、ルートに到達するまでツリーがトラバースされることが必要である。ツリー構造のトラバースには、バイナリツリーがファイルに格納されることが必要であり、ツリーがトラバースされるときにメモリへの多数のアクセスが必要である。
【０００４】
図１は、ハフマン符号化によって生成された「コードツリー」の一例を例示する。ノードは、円のＯおよび正方形でマークが付けられたポイントである。複数のノードを接続する線分は「ブランチ」と呼ばれる。最高位置に位置するノードは「ルート」と呼ばれる。さらに、「ブランチ」を介してノードＸに接続された下のノードＹは、ノードＸの「子」と呼ばれる。逆に、ノードＸはノードＹの「親」と呼ばれる。「子」を有していないノードは「リーフ」と呼ばれ、特定の文字は各「リーフ」に対応する。さらに、「リーフ」を除くノードは「内部ノード」と呼ばれ、「ルート」から各「ノード」までの「ブランチ」の数はレベルと呼ばれる。
【０００５】
コードツリーの使用によって符号化されるとき、「ルート」から目標の「リーフ」（符号化される文字に対応する）にまで伸びるパスがコードとして出力される。具体的には、各ノードから左側へ、「ルート」から目標の「リーフ」まで下にブランチするとき、「１」が出力され、右側にブランチするとき、「０」が出力される。たとえば、図１に例示するコードツリーでは、ノード番号７の「リーフ」に対応する文字Ａについてコード「００」が出力され、ノード番号８の「リーフ」に対応する文字Ｂについてコード「０１１」が出力される。
【０００６】
復号化されるとき、復号化のための目標として定義されたコードの各ビットの値に従って、「ルート」から各ノードをトレースすることによって到達する「リーフ」に対応する、文字が出力される。
【０００７】
大まかに言えば、ハフマン符号化アルゴリズムは、上述のコードツリーを以下に従って生成する。
（１）個々の文字に対応するリーフノードが準備され、各リーフに対応する文字の発生の頻度が記録される。
【０００８】
（２）１つの新しいノードが、最低発生頻度を有する２つのノードについて作成され、この作成されたノードがブランチを介してこの２つのノードに接続される。さらに、ブランチを介して接続されたこの２つのノードの発生頻度の和が、新たに作成されたノードの発生頻度として記録される。
【０００９】
（３）項目（２）で述べた処理が、残りのノード、すなわち親を有していないノードについて、残りのノードの数が１になるまで実行される。
このように生成されたコードツリーでは、１つのコードが各文字に割り振られ、そのコード長は文字の発生頻度に反比例する。したがって、符号化がコードツリーの使用によって実行されるとき、その後に続いてデータを圧縮することができる。
【００１０】
このデータを、使用する前に圧縮解除しなければならない。
ハフマン符号化アルゴリズムは１９５０年代早期に紹介された。その後数年間、これがカノニカル形式を含むように特徴付けられ、分析され、拡張されてきた。カノニカル・ハフマン・コードは最適なプレフィックスなしのコードであるが、このコードは標準のハフマン符号化を使用して生成されない。その代わりに、ハフマンのアルゴリズムが使用されて、各コードワードのビットの長さが計算されるが、異なるアルゴリズムが使用されて実際のコードワードが決定される。これらのコードワードは、いつコードワードが組み立てられているかを決定するために必要とされるものが小さいルックアップテーブルのみであるように選択され、次いで復号化されたシンボルに、復号化されたシンボルを含む別の小さいルックアップテーブルから直接アクセスすることができる。
【００１１】
図２に示すように、カノニカル・ハフマン符号化ファイルは３つのテーブル、すなわちＦＩＲＳＴＣＯＤＥテーブル１、ＳＹＭＢＯＬ  ＰＯＩＮＴＥＲテーブル２およびＳＹＭＢＯＬテーブル３、および圧縮されたデータからなる。ＦＩＲＳＴＣＯＤＥテーブル１は、所与の長さの各コードワードについて、それに割り当てられた１つのエントリを有する。たとえば、最長コードワードの長さが１０ビットである場合、ＦＩＲＳＴＣＯＤＥテーブル１は１０個のテーブルエントリを有するようになる。ＦＩＲＳＴＣＯＤＥテーブル１は、最初に長さ１のためのコードから下に長さＮのためのコードまでにより編成される。このテーブルにおける値が使用されて、いつコードワードが復号化のために構築されているかが決定される。コードワードは可変長であり、区切り文字が使用されないので、コードワードビットパターンおよびＦＩＲＳＴＣＯＤＥテーブル１により、いつコードワードの最後に到達しているかを決定することが可能となる。ＦＩＲＳＴＣＯＤＥテーブル１における値は、そのビット長のコードワードの最小整数値に等しい。すなわち、組み立てられたビットの整数値がＦＩＲＳＴＣＯＤＥ内の値以上であるときにビットを組み立てるとき、有効なコードワードが復号化のために使用可能である。
【００１２】
第２のテーブルであるＳＹＭＢＯＬ  ＰＯＩＮＴＥＲテーブル２は、各ビット長についての最初に復号化されたシンボルへのポインタを含む。ＳＹＭＢＯＬ  ＰＯＩＮＴＥＲテーブル２は各ビット長について１つのワードを含む。
【００１３】
ＳＹＭＢＯＬテーブル３は、実際に復号化されたシンボル値を含む。ＳＹＭＢＯＬテーブル３の長さは、復号化するシンボルの数に等しい。ＳＹＭＢＯＬテーブル３は、アドレスによって索引付けされた、解決されたシンボルのルックアップテーブルである。
【００１４】
これらの３つの各テーブルがメモリに格納される。圧縮されたデータが読み取られ、圧縮解除アルゴリズムが使用されて、元のデータが抽出される。
図２は従来のカノニカル復号化アルゴリズムを指し、ＬＥＮＧＴＨ  ＣＯＵＮＴＥＲ４および作業値Ｖが０にリセットされる。圧縮されたデータの次のビットがＶに、加算関数５を使用して加算される。比較関数６を使用して、加算関数５の結果が、ＬＥＮＧＴＨ  ＣＯＵＮＴＥＲ４によって選択されたＦＩＲＳＴＣＯＤＥ値と比較される。この比較（Ｖ＞＝ＦＩＲＳＴＣＯＤＥ（Ｌ））がＦＡＬＳＥである場合、ＬＥＮＧＴＨ  ＣＯＵＮＴＥＲ４が増分され、左シフト演算７を使用して作業値に２が掛けられ、圧縮されたデータ８から次に圧縮されたビットが、シフトされた値に加算される。比較関数６を使用して、結果が再度ＦＩＲＳＴＣＯＤＥ（Ｌ）と比較される。このプロセスが、比較（Ｖ＞＝ＦＩＲＳＴＣＯＤＥ（Ｌ））がＴＲＵＥになるまで、繰り返される。
【００１５】
比較がＴＲＵＥであるとき、ＳＹＭＢＯＬ  ＰＯＩＮＴＥＲテーブル２からの値がＬＥＮＧＴＨ  ＣＯＵＮＴＥＲによって選択され、加算関数９を使用して作業値Ｖに加算される。ＬＥＮＧＴＨ  ＣＯＵＮＴＥＲ４によって選択されたＦＩＲＳＴＣＯＤＥ値が、減算関数１０を使用して減算され、結果の値はＳＹＭＢＯＬテーブル３のためのアドレスであり、それによりＳＹＭＢＯＬが解決される。したがって、このアルゴリズムは本質的に、ＳＹＭＢＯＬを解決するために最大Ｎ回の反復を取ることができるビット比較プロセスである。
【００１６】
圧縮解除または「復号化」の手順を、以下の表１におけるＣ言語の擬似コードによって説明することができる。この擬似コードでは、関数が、上述のような従来のカノニカル・ハフマン復号化アルゴリズムを実行し、解決されたＳＹＭＢＯＬを戻す。
【００１７】
表１：従来のカノニカル圧縮解除アルゴリズム擬似コード
ＶおよびＬＥＮＧＴＨ  ＣＯＵＮＴＥＲ値Ｌをそれらの基準値に初期化する
ＶをＮＥＸＴＩＮＰＵＴＢＩＴ（）値に設定する
Ｖ＜ＦＩＲＳＴＣＯＤＥ（Ｌ）である間
ＶをＶ＊２＋ＮＥＸＴＩＮＰＵＴＢＩＴ（）に設定する
Ｌ＝Ｌ＋１
ＳＹＭＢＯＬ＝ＳＹＭＢＯＬ  ＰＯＩＮＴＥＲ  ＴＡＢＬＥ（Ｌ）＋Ｖ−ＦＩＲＳＴＣＯＤＥ（Ｌ）を戻す
有効であるが、このソフトウェア圧縮解除は時間がかかり、ソフトウェアが圧縮解除中に他のタスクを実行することが妨げられる。
【発明の開示】
【発明が解決しようとする課題】
【００１８】
本発明は、圧縮されたカノニカル・ハフマン符号化データの圧縮解除のための高速手段を提供し、これは、データを圧縮するための高速周辺装置を提供し、それにより従来のデバイスおよび方法と対照的に、他の作業を行うためにメインプロセッサをオフロードすることによって行う。本発明はまた多数の専用圧縮解除周辺装置にも備えて、多数のデータ要求者を有するアプリケーションにおいて圧縮解除のパフォーマンスをさらに増す。
【００１９】
本発明の圧縮解除アルゴリズムはハードウェアにおいて実施されて、従来のソフトウェアの解決法よりはるかに高速である圧縮解除オペレーションの並列処理が提供され、これは多数の並列パスおよび機能ブロックが利用されて、圧縮解除が高速に実施されるからである。
【課題を解決するための手段】
【００２０】
本発明の一態様によれば、本発明の圧縮解除アルゴリズムは、圧縮されたカノニカル・ハフマン符号化データの圧縮解除のための圧縮解除デバイスとして実施され、ＦＩＲＳＴＣＯＤＥと圧縮されたデータビットの間で関係が、ＦＩＲＳＴＣＯＤＥ［０］およびビット０、ＦＩＲＳＴＣＯＤＥ［１］およびビット０、１、ＦＩＲＳＴＣＯＤＥ［２］およびビット０、１、２、からＦＩＲＳＴＣＯＤＥ［Ｎ］およびビット０、１、２、．．．Ｎに従って固定され、ＦＩＲＳＴＣＯＤＥとＳＹＭＢＯＬ  ＰＯＩＮＴＥＲの間で関係が、ＦＩＲＳＴＣＯＤＥ［０］およびＳＹＭＢＯＬ  ＰＯＩＮＴＥＲ［０］、ＦＩＲＳＴＣＯＤＥ［１］およびＳＹＭＢＯＬ  ＰＯＩＮＴＥＲ［１］、からＦＩＲＳＴＣＯＤＥ［Ｎ］およびＳＹＭＢＯＬ  ＰＯＩＮＴＥＲ［Ｎ］に従って固定される。したがって、本発明のデバイスは、各々がそれに関連付けられたＦＩＲＳＴＣＯＤＥ値を有する複数のＦＩＲＳＴＣＯＤＥレジスタと、各々がそれに関連付けられたＳＹＭＢＯＬ  ＰＯＩＮＴＥＲ値を有する複数のＳＹＭＢＯＬ  ＰＯＩＮＴＥＲレジスタと、各々が、そこからＦＩＲＳＴＣＯＤＥ値を受け入れるように異なるＦＩＲＳＴＣＯＤＥレジスタに結合され、その中に格納された圧縮されたカノニカル・ハフマン符号化データを有するメモリデバイスから、圧縮されたデータビットのストリングを受け入れるように結合された、複数の比較器であって、複数のＦＩＲＳＴＣＯＤＥ値を、圧縮されたデータビットのストリングの対応するビットと同時に比較するように構成される比較器と、各比較器の結果を受け入れるように結合されたマルチプレクサであって、結果を順次検査するように、かつ成功した比較結果を選択するように構成されるマルチプレクサと、各々がＳＹＭＢＯＬ  ＰＯＩＮＴＥＲレジスタのうち異なる１つに結合された複数の加算ブロックであって、その加算ブロックの１つは、ＦＩＲＳＴＣＯＤＥレジスタのうち成功した比較結果を有する１つに対応するＳＹＭＢＯＬ  ＰＯＩＮＴＥＲレジスタに関連付けられ、対応するＳＹＭＢＯＬ  ＰＯＩＮＴＥＲレジスタからの値を、圧縮されたＮＥＸＴＩＮＰＵＴＷＯＲＤデータビットのストリングに加算するように構成される加算ブロックと、各々がＦＩＲＳＴＣＯＤＥレジスタのうち異なる１つに、かつＦＩＲＳＴＣＯＤＥレジスタのうち１つに対応する加算ブロックの１つに結合された複数の減算ブロックであって、その減算ブロックの１つは、ＦＩＲＳＴＣＯＤＥレジスタのうち成功した比較結果を有する１つに関連付けられ、成功したＦＩＲＳＴＣＯＤＥレジスタの値を対応する加算ブロックの結果から減算するように、かつ入力アドレスをマルチプレクサに出力するように構成される減算ブロックと、入力アドレスを受信するようにマルチプレクサに結合され、応答して、対応する解決されたシンボルを出力するように構成されるＳＹＭＢＯＬテーブルとを含む。
【００２１】
加算および減算の順序は本発明にとって重要ではない。したがって、加算関数が減算関数に先んじてもよく、加算および減算関数は本発明によれば順序付けされない。むしろ、圧縮されたデータが結果に加算される前に、ＦＩＲＳＴＣＯＤＥレジスタをＳＹＭＢＯＬ  ＰＯＩＮＴＥＲレジスタから減算することができる。
【００２２】
本発明のもう１つの態様によれば、本発明は、カノニカル・ハフマン符号化データの圧縮解除のための方法を提供する。
本発明のさらにもう１つの態様によれば、プロセッサがメモリデバイスに結合され、論理デバイスを動作する。圧縮解除デバイスがさらにメモリに結合され、これはそれぞれカノニカル・ハフマン符号化データファイルを受信し、解決されたシンボルを出力するためである。
【００２３】
前述の態様および本発明に伴う利点の多数は、以下の詳細な説明が添付の図面と共に考慮されるとき、これを参照することによってよりよく理解されるので、より容易に理解されるであろう。
【発明を実施するための最良の形態】
【００２４】
図面において類似の番号は類似の要素を示す。
本発明は、従来の圧縮解除方法よりはるかに高速に圧縮データシンボルを解決する、圧縮解除アルゴリズムのための装置および方法である。従来の圧縮解除は、同じアルゴリズムを使用してソフトウェアにおいてもハードウェアにおいても実施することができる。しかし、ソフトウェア実施は従来の圧縮解除に限定され、これはこのアルゴリズムが直列または逐次ループ方法で実行されなければならないからである。対照的に、本発明の新規な圧縮解除アルゴリズムは、圧縮されたデータとカノニカル・ハフマン符号化データのテーブルの間の関係を使用して利益を得ることを可能にする、ハードウェアにおいて実施される。これらの関係により、いくつかのオペレーションを並列に実行して、本発明のハードウェア実施がソフトウェアの解決法より高速に動作するようにすることが可能である。
【００２５】
また、本発明のハードウェア解決法が随意に多くの回数でインスタンス化されて、データを同時に要求する多数のアプリケーションを有するホストシステムの要件を満たすために十分な処理能力が提供される。
【００２６】
図３は、カノニカル・ハフマン符号化データの圧縮解除のためのアルゴリズムの多数のハードウェアインスタンス化として実施された、本発明の圧縮解除装置２０を例示する。図３に例示した本発明の実施形態によれば、圧縮解除アルゴリズムがハードウェアにおいて、多数の並列パスおよび機能ブロックを使用して実施されて、圧縮解除が高速に実施される。
【００２７】
本発明のハードウェア実施の圧縮解除アルゴリズムは、表２に示すＦＩＲＳＴＣＯＤＥと圧縮されたデータビット、および、表３に示すＦＩＲＳＴＣＯＤＥとＳＹＭＢＯＬ  ＰＯＩＮＴＥＲの間の関係を利用する。
【００２８】
表２：ＦＩＲＳＴＣＯＤＥおよび圧縮されたデータビットの関係
ＦＩＲＳＴＣＯＤＥ［０］およびビット０、
ＦＩＲＳＴＣＯＤＥ［１］およびビット０、１、
ＦＩＲＳＴＣＯＤＥ［２］およびビット０、１、２など、
からＦＩＲＳＴＣＯＤＥ［Ｎ］およびビット０、１、．．．Ｎ。
【００２９】
表３：ＦＩＲＳＴＣＯＤＥおよびＳＹＭＢＯＬ  ＰＯＩＮＴＥＲの関係
ＦＩＲＳＴＣＯＤＥ［０］およびＳＹＭＢＯＬ  ＰＯＩＮＴＥＲ［０］、
ＦＩＲＳＴＣＯＤＥ［１］およびＳＹＭＢＯＬ  ＰＯＩＮＴＥＲ［１］など、
からＦＩＲＳＴＣＯＤＥ［Ｎ］およびＳＹＭＢＯＬ  ＰＯＩＮＴＥＲ［Ｎ］。
【００３０】
すべての計算の並列実行が可能となり、これは表２および３に示す関係が固定されるからである。並列実行は、新しいＮＥＸＴＩＮＰＵＴＷＯＲＤが提示されるときには直ちにシンボルが発見される結果となり、ただし各ＮＥＸＴＩＮＰＵＴＷＯＲＤは、Ｎビット長の圧縮されたデータのストリングまたは「ワード」であり、たとえば、８、１６、３２または６４ビット長である。すなわち、ＳＹＭＢＯＬを解決するために反復が必要とされず、従来の圧縮解除アルゴリズムのソフトウェア実施によって必要とされた反復ビット比較プロセスが除去される。
【００３１】
知られているように、カノニカル・ハフマン符号化ファイルは３つのテーブル、すなわちＦＩＲＳＴＣＯＤＥテーブル１、ＳＹＭＢＯＬ  ＰＯＩＮＴＥＲテーブル２およびＳＹＭＢＯＬテーブル３、および圧縮されたデータ８からなる。本発明によれば、ＦＩＲＳＴＣＯＤＥテーブル１およびＳＹＭＢＯＬ  ＰＯＩＮＴＥＲテーブル２がメモリから読み取られ、レジスタ２１［０］、２１［１］、．．．２１［Ｎ］および２２［０］、２２［１］、．．．２２［Ｎ］にそれぞれロードされる。ＳＹＭＢＯＬテーブル３は、図２の従来の圧縮解除アルゴリズムで説明したように、すなわち、解決されたシンボルのルックアップテーブルとして再度実施される。ＳＹＭＢＯＬテーブル３はメモリに格納され、アドレスによりアクセスされる。圧縮されたデータ８は圧縮解除回路２０に、Ｎビット長のワードとして提示される。各ＦＩＲＳＴＣＯＤＥレジスタ２１［０］、２１［１］、．．．２１［Ｎ］は、各ＦＩＲＳＴＣＯＤＥ値を各比較器２３［０］、２３［１］、．．．２３［Ｎ］に提示するように結合される。ＦＩＲＳＴＣＯＤＥ値が、圧縮されたデータ８の関連付けられたＮＥＸＴＩＮＰＵＴＷＯＲＤビットと比較され、すべての比較器２３［０］、２３［１］、．．．２３［Ｎ］は同時に動作する。
【００３２】
各比較器２３［０］、２３［１］、．．．２３［Ｎ］は、その各比較結果をマルチプレクサ２４に出力する。マルチプレクサ２４は、比較器２３［０］から開始して比較器２３［Ｎ］に向かって進行しながら、比較結果を検査する。成功またはＴＲＵＥである比較結果を有する、最初に遭遇された値が、正しい解である。入力アドレスは、圧縮されたデータ８のＮＥＸＴＩＮＰＵＴＷＯＲＤビットおよび関連付けられたＦＩＲＳＴＣＯＤＥ値を、関連付けられたＳＹＭＢＯＬ  ＰＯＩＮＴＥＲ値により、順序付けなしに加算かつ減算することである。マルチプレクサ２４は対応する入力アドレスをＳＹＭＢＯＬテーブル３に向けて送り、これが応答して、解決されたＳＹＭＢＯＬを出力する。
【００３３】
したがって、加算および減算ブロック２５［０］、２５［１］、．．．２５［Ｎ］および２６［０］、２６［１］、．．．２６［Ｎ］はそれぞれ、圧縮されたデータ８の圧縮解除において使用される。ＴＲＵＥ比較結果を有するＦＩＲＳＴＣＯＤＥレジスタ２１［Ｘ］からの値に対応する、ＳＹＭＢＯＬ  ＰＯＩＮＴＥＲテーブルレジスタ２２［Ｘ］からの値が、マルチプレクサ２４によって選択され、対応する加算ブロック２５「Ｘ」を使用して、圧縮されたデータ８に加算される。対応する減算ブロック２６［Ｘ］を使用して、対応するＦＩＲＳＴＣＯＤＥレジスタ２１［Ｘ］からの値が、加算の結果、すなわち加算ブロック２５［Ｘ］の出力から減算される。減算ブロック２６［Ｘ］の結果は、マルチプレクサ２４によってＳＹＭＢＯＬテーブル３にアクセスするために使用された入力アドレスを表す。ＳＹＭＢＯＬテーブル３は、入力アドレスに対応するシンボルを出力する。すなわち、減算ブロック２６［Ｘ］の出力は、ＳＹＭＢＯＬテーブル３における対応するシンボルへの入力アドレスであり、ＳＹＭＢＯＬテーブル３は解決されたＳＹＭＢＯＬを出力する。
【００３４】
本発明は、ＳＹＭＢＯＬ  ＰＯＩＮＴＥＲテーブルレジスタ２２［Ｘ］からの値を、圧縮されたデータ８に加算させ、次いで、対応するＦＩＲＳＴＣＯＤＥレジスタ２１［Ｘ］からの値を結果から減算させることとして説明され、減算の結果は、マルチプレクサ２４によってＳＹＭＢＯＬテーブル３にアクセスするために使用された入力アドレスである。しかし、加算および減算演算の順序は重要ではなく、本発明の代替実施形態において逆にすることができる。すなわち、成功またはＴＲＵＥ比較結果を有するＦＩＲＳＴＣＯＤＥレジスタ２１［Ｘ］からの値がＳＹＭＢＯＬ  ＰＯＩＮＴＥＲテーブルレジスタ２２［Ｘ］から減算され、この結果が次いで、圧縮されたデータ８に加算される。したがって、減算ブロック２６［Ｘ］ではなく、加算ブロック２５［Ｘ］の結果が、マルチプレクサ２４によってＳＹＭＢＯＬテーブル３にアクセスするために使用された入力アドレスを表す。
【００３５】
強化型対地接近警報システム（ＥＧＰＷＳ）における実施態様
危険な飛行状態の場合に警報または助言（advisory)指示を提供する様々なシステムが知られている。このようなシステムの中には、一般に航空機用の対地接近警報システム（ＧＰＷＳ）として知られるシステムがあり、これらは航空機の飛行状態を監視し、飛行状態が、地表との不注意な接触が差し迫っているような場合、警報を提供する機能を果たす。このようなシステムによって監視される飛行状態には電波高度およびレート、気圧高度およびレート、対気速度、および、フラップおよびギア位置がある。前述のパラメータが監視され、前述の状態またはパラメータの間の関係が、地上衝突が起こる可能性があるとき、助言指示または警報が生成される。このようなシステムの典型的な実施例は、米国特許第３，７１５，７１８号、第３，９３６，７９６号、第３，９５８，２１８号、第３，９４４，９６８号、第３，９４７，８０８号、第３，９４７，８１０号、第３，９３４，２２１号、第３，９５８，２１９号、第３，９２５，７５１号、第３，９３４，２２２号、第４，０６０，７９３号、第４，０３０，０６５号、第４，２１５，３３４号および第４，３１９，２１８号で開示されており、これらはすべて本発明の譲受人に譲渡され、全体として参照により本明細書に組み込まれる。このようなシステムの追加の実施例は、米国特許第３，３４９，７５１号、第３，９８８，７１３号、第４，１８９，７７７号、第４，４３３，３２３号、第４，４９５，４８３号、第４，６８４，９４８号、第４，８４９，７５６号、第４，８５７，９２３号、第４，９１４，４３６号、第５，１６６，６８２号、第５，１９６，８４７号、第５，２２０，３２２号、第５，４２８，３５４号、第５，７８１，１２６号および第６，１５７，８９１号で開示されており、これらはすべて本発明の譲受人によって所有され、全体として参照により本明細書に組み込まれる。
【００３６】
上記のシステムは助言および警報信号を地形接近の場合に提供するが、このようなシステムは警報を、航空機の飛行状態に基づいて生成し、航法情報を利用しない。したがって、このようなシステムの感度は、危険な飛行状態が存在するときに適切な警報を提供するように、危険がないときには誤った、あるいは不快な警報を生成することのないように調整される。
【００３７】
特定の地理上の区域に固有の地形上を、他の地理上の区域における所望の警報時間より短く飛行中であるときに、不快な警報のいくつかを修正しようとする１つの試みは、その上を航空機が飛行中である特定の地理上の区域についての警報基準を最適化するために、航空機の地理的位置に従って対地接近警報システムの警報基準を修正することであった。このようなシステムの一実施例は米国特許第４，５６７，４８３号に記載されており、これは本発明の譲受人に譲渡され、全体として参照により本明細書に組み込まれる。米国特許第４，５６７，４８３号で開示されたシステムでは、警報基準が、ある限定された区域についての地形特性、特に、不快な警報および他の問題に遭遇している特定の空港の特性に適合するように最適化される。
【００３８】
地理的入力を利用するもう１つの手法は、米国特許第４，２２４，６６９号で使用されており、これは全体として参照により本明細書に組み込まれ、これにおいてはメモリデバイスが使用されて、地理座標区域により最低安全高度が格納される。航法コンピュータが使用されて航空機の位置が決定され、航空機が飛行中である座標区域について格納された最低安全高度より低く降りる場合、警報が与えられる。このシステムは「最悪の場合」および「戦術」モードのオペレーションを含む。「最悪の場合」モードでは、最低安全高度が、所定の地理座標区域内で最も高い地形または障害物に応じて決定される。「戦術」モードの動作では、位置、対地速度およびグラウンドトラックなどの現行の飛行状態が使用されて、計画された飛行経路のすぐ前方の地形および障害物の既知の高さに基づいて、最低安全高度が定義される。
【００３９】
米国特許第４，６７５，８２３号は本発明の譲受人に譲渡され、全体として参照により本明細書に組み込まれており、地理的な位置データを利用して特定の地理上の区域の地形の既知の高さに従って警報基準を変更する対地接近警報システムを記載している。簡単に述べると、航空機が特定の地理上の区域内にあるかどうかの決定が、所定の世界または地理上の区域を複数のゾーンに細分させ、さらにこれらが領域および区域に細分されることによって、提供される。領域内の各区域が、ゾーン内のその位置およびその形状によって定義され、形状はいくつかの標準形状の１つとして定義され、これは正方形、平行四辺形、三角形、円、扇形、楕円または他の形状などである。このようなデータ記憶フォーマットゾーン、領域または区域の使用により、様々な区域を定義するために必要とされるデータの量が減り、警報基準の修正を必要とする区域内に航空機があるかどうかを決定するために必要とされる計算時間が減る。データ圧縮の使用により、ゾーン、領域および区域情報、および対応する地形および障害物の高さを保持するために必要とされる記憶空間の量が減る。しかし、この圧縮されたデータは、使用前に圧縮解除されなければならない。
【００４０】
図４は、地理上の区域の決定を有する対地接近警報システムの一実施形態を例示する機能ブロック図であり、これは強化型対地接近警報システム（ＥＧＰＷＳ）としても知られ、本発明の周辺圧縮解除装置２０を含み、強化型対地接近警報システムの全体が参照番号１００によって示される。基礎をなす強化型対地接近警報システム１００は、上記の組み込まれた米国特許第４，６７５，８２３号でより十分に説明されている。航空機データバス１１０は様々な信号を対地接近警報システム１００に提供する。対地接近警報システムで使用可能な信号の詳細な説明は、Ａｅｒｏｎａｕｔｉｃａｌ  Ｒａｄｉｏ，Ｉｎｃｏｒｐｏｒａｔｅｄ  ｏｆ  Ａｎｎａｐｏｌｉｓ，Ｍｄ．によって発行された「ＡＲＩＮＣ  Ｃｈａｒａｃｔｅｒｉｓｔｉｃ  ４２９」において提供される。航空機データバス１１０によって提供される信号には、気圧および電波高度信号、垂直速度信号、コース、飛行方向、緯度および経度信号、電波グライドスロープ信号、フラップおよびギア位置信号、およびローカライザ受信器信号が含まれる。これらの信号が警報論理回路への入力として使用され、この回路は、航空機が地形に関して安全でない状態にあることを様々な飛行パラメータが指示するときに、助言または警報信号を生成するために有効である。助言または警報信号が音声警報発生器に加えられ、これは音声警報信号を生成し、この結果として音声警報がコックピットのスピーカを用いてアナウンスされる。
【００４１】
たとえば、図４で実施した警報システム１００は、エアデータコンピュータ１１２から、あるいは、航空機上に存在して航空機の気圧高度および航空機の垂直速度についての情報を提供する気圧高度計および気圧レート回路からのデータを使用する。垂直速度を気圧レートとして、あるいはＺ速度として表すことができ、これはオンボードの慣性航法システムから得ることができる。データはまた航空機上の航法システム１１４からも受信されて、航空機のコース、飛行方向、緯度および経度についての情報が提供される。航法データを直接、慣性航法システム、衛星航法受信器、ＶＬＦ／ＯＭＥＧＡ、Ｌｏｒａｎ  Ｃ、ＶＯＲ／ＤＭＥまたはＤＭＥ／ＤＭＥを含むことができる航法システムから、あるいは飛行管理システムから得ることができる。加えて、警報システム１００は、電波高度計１１６、グライドスロープ受信器１１８からの信号、および、フラップおよびランディング・ギアの位置を示すディスクリート１２０および１２２からのディスクリート信号を利用する。また、ローカライザ受信器１２４からの信号も使用され、これは、航空機が着陸のための正しいコース上にあるかどうかを指示する。
【００４２】
警報システム１００を本明細書で航空機環境において説明するが、警報システム１００はまた、たとえば潜水艦など、地形の周囲で航行しなければならない他の車両についても使用可能である。エアデータコンピュータ１１２、電波高度計１１６、グライドスロープ受信器１１８、および、フラップおよびランディング・ギア・ディスクリート１２０および１２２からの信号は、警報論理回路または警報発生器１２６に加えられる。警報発生器１２６は、全体として対地接近警報システムとして知られるシステムの一部を形成することができ、その実施例は先に参照した特許で開示されており、これは、それに加えられた信号が危険な飛行状態を示すときに警報を開始する。このような危険な状態が検出されるとき、警報開始信号が音声発生器１２８に加えられ、これが適切な音声警報を直接、あるいは航空機の相互通信システムを介してスピーカ・トランスデューサ１３０に加え、それにより警報をパイロットに知らせる。
【００４３】
警報発生器１２６は、警報システム１００に従って、様々な危険な飛行状態が起こるときに警報を開始する。警報を開始させることができる危険な飛行状態の中には、離陸後の負の上昇、不十分な地形のクリアランス、過大な降下率、過大なクロージャ率、およびグライドスロープより低い進入がある。このような警報を開始するための基準は、アナログ警報発生器における所定のコンポーネント値によって、かつデジタル警報発生器に格納されたデータによって定義され、これは警報基準を明確に定義し、これを「警報エンベロープ」として知られるグラフとしてグラフ表現することができる。このような警報エンベロープの実施例は、米国特許第３，９３６，７９６号で開示されており、これは参照により本明細書に組み込まれる。
【００４４】
対地接近警報システムの警報基準または警報エンベロープは、警報時間を最大限にすると同時に誤った、あるいは不快な警報を最小限にするように調整される。しかし、すべてのタイプの地形について最適である警報エンベロープは調整することができず、したがって、大抵の警報エンベロープは、大抵の飛行状態下で満足の行くパフォーマンスを可能にする折衷の結果であるが、これらはある通常でない地理上の区域には最適でない可能性もある。したがって、ある所定の地理上の区域で起こる通常でない地形特性について警報エンベロープを最適化するために、航法システム１１４からの信号、ならびに他の信号を受信し、警報発生器１２６によって警報を開始するために使用される警報基準または警報エンベロープを、航空機の地理的位置に従って修正するシステム１４０が提供される。システム１４０はメモリ１４２を含み、これは、エンベロープ修正を必要とし、ならびに警報修正が必要とされる区域の圧縮された地形標高データ、すなわち場所および境界を格納する。場所探索論理１４４が、航空機の位置を監視するために使用されて、エンベロープ修正を必要とする区域内に航空機があるかどうかを決定するようにされる。航空機がこのような区域内にある場合、論理１４４は警報修正を、ある他の基準が満たされていない場合に修正を抑止する警報修正回路１４６を介して開始する。前述の他の基準は、米国特許第４，６７５，８２３号でより詳細に論じられている。十分に正確な航法データが使用可能である場合、高度修正器１４８を利用して、既知の標高の地形上の電波高度を測定することによって取られた高度読み取りに対応するように、気圧高度読み取りを修正することができる。そうでない場合、警報修正は単に、既知の地形上の気圧高度読み取りと電波高度読み取りの間に矛盾がある場合に、抑止される可能性がある。
【００４５】
前述のように、メモリ１４２は、警報エンベロープ修正が望ましい区域の場所および境界を含む。このような区域の場所が航空機の現在位置と比較されて、エンベロープ修正が必要であるかどうか、およびこのような修正の性質が決定される。しかし、航空機の現在位置を、エンベロープ修正が必要とされる各区域の場所と絶えず比較することには、過大な計算能力または過大な計算時間が必要となり、これは対地接近警報システムの物理的かつ時間の要件とは合わなくなる。したがって、エンベロープ修正を必要とする区域の場所および境界を単に格納するのではなく、世界が複数の緯度帯に分割され、これがさらに所定の経線によって複数のゾーンに分割され、これがさらに複数の領域に分割され、この領域が、警報エンベロープ修正を必要とする１つまたは複数の区域を含むことができ、これはより詳細に米国特許第４，６７５，８２３号で説明されている。
【００４６】
本発明の一実施形態によれば、本発明の圧縮解除装置２０は、メモリ１４２に格納された圧縮された地形データを圧縮解除するために、場所探索論理１４４を動作するメインプロセッサとメモリ１４２の間に結合された、高速周辺デバイスを提供する。本発明の圧縮解除装置２０はこれによりメインプロセッサをオフロードし、それが場所探索論理１４４を動作することおよび他の作業を行うことを可能にする。圧縮解除装置２０は、所定の区域、領域またはゾーンに対応する地形データを取り出して圧縮解除するための要求またはコマンドを、メインプロセッサから受信する。圧縮解除装置２０は、圧縮されたデータファイルをメモリ１４２から検索し、圧縮解除機能を実行し、圧縮解除されたデータをメモリ１４２へ一時的に格納するために戻す。圧縮解除装置２０はまた、圧縮解除機能の完了をメインプロセッサにレポートすることもできる。このように、圧縮解除されたデータは、要求に応じてメインプロセッサで使用可能である。
【００４７】
さらに、本発明の圧縮解除アルゴリズムはハードウェアデバイス２０において実施されるとき、従来のソフトウェアの解決法よりはるかに高速であり、これは多数の並列パスおよび機能ブロックが利用されて圧縮解除が高速に実施され、いくつかのオペレーションを直列の方法ではなく並列に実行することが可能となるからである。たとえば、ソフトウェアは５０から１００クロックまでのいずれかを要して地形標高を解くことができるが、ハードウェアデバイス２０は８クロック未満を要する。また、圧縮解除のパフォーマンスが増すことは、圧縮解除された地形データを多数の要求者に提供するために大変有用である。したがって、ハードウェア解決法がオプショナルで必要な回数でインスタンス化されて、警報システム１００の要件を満たすために十分な処理能力が提供される。たとえば、本発明の多数の専用圧縮解除装置２０がオプショナルでインスタンス化されて、圧縮解除のパフォーマンスがさらに増す。
【００４８】
本発明の好ましい実施形態を例示し、説明したが、ここにおいて本発明の精神および範囲から逸脱することなく様々な変更を行うことができることは理解されよう。
【図面の簡単な説明】
【００４９】
【図１】コードツリーを示す説明図である。
【図２】カノニカル・ハフマン形式で符号化されたデータを圧縮解除するための従来の復号化アルゴリズムを示す説明図である。
【図３】カノニカル・ハフマン符号化データの圧縮解除のためのアルゴリズムの多数のインスタンス化として実施された、本発明の圧縮解除装置の図である。
【図４】地理上の区域の決定を有する対地接近警報システムの一実施形態を例示し、本発明の周辺圧縮解除装置を含む機能ブロック図である。
【図１】
2004528771.tif 000003
【図２】
2004528771.tif 000004
【図３】
2004528771.tif 000005
【図４】
2004528771.tif 000006
【国際公開パンフレット】
2004528771.tif 000007
2004528771.tif 000008
2004528771.tif 000009
2004528771.tif 000010
2004528771.tif 000011
2004528771.tif 000012
2004528771.tif 000013
2004528771.tif 000014
2004528771.tif 000015
2004528771.tif 000016
2004528771.tif 000017
2004528771.tif 000018
2004528771.tif 000019
2004528771.tif 000020
2004528771.tif 000021
2004528771.tif 000022
2004528771.tif 000023
2004528771.tif 000024
2004528771.tif 000025
2004528771.tif 000026
2004528771.tif 000027
2004528771.tif 000028
2004528771.tif 000029
2004528771.tif 000030
2004528771.tif 000031
2004528771.tif 000032
2004528771.tif 000033
【国際公開パンフレット（コレクトバージョン）】
2004528771.tif 000034
【国際調査報告】
2004528771.tif 000035
2004528771.tif 000036
2004528771.tif 000037