デコーダ回路及びデコード方法
【課題】 LZ77法を採用して圧縮したデータを復号するデコーダ回路等において、復号処理の高速化を実現する。
【解決手段】 辞書4から読み出された単位データを遅延させる第1の遅延手段2と、データを選択する選択手段10と、選択手段10によって選択されたデータを遅延させる第2の遅延手段3とを備え、辞書4には、第2の遅延手段3からの遅延データが書き戻され、選択手段10は、第1の遅延手段2からの遅延データと第2の遅延手段3からの遅延データとが入力され、辞書4の読出しアドレスと書込みアドレスとが遅延手段2及び4での遅延量に応じた所定の近さの範囲内にある場合には第2の遅延手段3からの遅延データを選択し、それ以外の場合には第1の遅延手段2からの遅延データを選択する。
【解決手段】 辞書4から読み出された単位データを遅延させる第1の遅延手段2と、データを選択する選択手段10と、選択手段10によって選択されたデータを遅延させる第2の遅延手段3とを備え、辞書4には、第2の遅延手段3からの遅延データが書き戻され、選択手段10は、第1の遅延手段2からの遅延データと第2の遅延手段3からの遅延データとが入力され、辞書4の読出しアドレスと書込みアドレスとが遅延手段2及び4での遅延量に応じた所定の近さの範囲内にある場合には第2の遅延手段3からの遅延データを選択し、それ以外の場合には第1の遅延手段2からの遅延データを選択する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、例えばLZ77法を採用して圧縮したデータを復号するデコーダ回路に関し、特に、復号処理の高速化を図ったものに関する。
【背景技術】
【0002】
辞書型のデータ圧縮アルゴリズムの一種として、LZ(Lempel-Ziv)77法が存在している。LZ77法は、例えばAITフォーマット,S−AITフォーマットまたはLTOフォーマットのテープドライブ内のALDC(Adaptive Lossless Data Compression)エンコーダ・ALDCデコーダなど、各種のデータ記録装置内のデータ圧縮・復号回路に採用されている(例えば、特許文献1参照。)。
【0003】
LZ77法の圧縮原理は、過去に入力された文字列(データ列)のうちの直近の所定サイズの文字列を辞書(ヒストリ・バッファ)に登録し、新たに入力された(すなわち、圧縮しようとする)文字列と一致する文字列をその辞書から検索して、当該新たに入力された文字列をその一致する文字列のアドレス情報で置き換えるというものである。この辞書は、静的なものではなく、圧縮が進むにつれて、今まさに圧縮しようとする文字列の直前の文字列を追加して古い文字列を除外するようにアップデートされるので、スライド辞書とも呼ばれる。
【0004】
図7は、この圧縮の様子を例示する図である。通常は辞書のサイズは512バイト,1024バイトまたは2048バイトであることが多いが、ここでは説明の都合上16バイトとしている。過去に入力された文字列のうちの直近の16文字の文字列「ABCCAB…BCC」(各文字A,B,Cは1バイト)が辞書として登録されている。16バイト前に入力された文字「A」にはアドレス0が付与されており、15バイト前に入力された文字「B」にはアドレス1が付与されており、1バイト前に入力された文字「C」にはアドレス15が付与されている。
【0005】
例えば、新たに入力された文字列が「ABCA」である場合には、検索の結果、辞書内のアドレス9〜12の文字列が「ABCA」と一致する。そこで、この場合には、検索結果を示す情報であるマッチアドレス(一致する文字列の最後のアドレスとして定義されるアドレス)として12を出力する。そして、最終的には、この文字列「ABCA」を、一致長4及び先頭アドレス9を示す符号語(Copy Pointer,Match Count=4,Match Address=9)に変換することにより、4バイトから2バイトに圧縮する。
【0006】
このようにして圧縮されたデータを復号するときには、逆に、この辞書を参照して、符号語(Copy Pointer,Match Count=4,Match Address=9)を文字列「ABCA」に変換する。その際、圧縮時の辞書のアップデートに対する逆の処理として、復号が進むにつれて、辞書の文字を書き換えることによって、圧縮時に使用した辞書を復元していく。
【0007】
図8〜図12は、この復号の様子を、図7に示した辞書と関連させて経時的に示す図である。まず、図8に示すように、読出しアドレスradrとして辞書のアドレス9(符号語が示すMatch Address=9)を指定するとともに、書込みアドレスwadrとして辞書のアドレス2を指定する。そして、図9に示すように、アドレス9から文字「A」を読み出し、この文字「A」をアドレス2に書き戻した後、読出しアドレスradr,書込みアドレスwadrとしてそれぞれアドレス10,3を指定する。
【0008】
続いて、図10に示すように、アドレス10から文字「B」を読み出し、この文字「B」をアドレス3に書き戻した後、読出しアドレスradr,書込みアドレスwadrとしてそれぞれアドレス11,4を指定する。
【0009】
続いて、図11に示すように、アドレス11から文字「C」を読み出し、この文字「C」をアドレス4に書き戻した後、読出しアドレスradr,書込みアドレスwadrとしてそれぞれアドレス12,5を指定する。
【0010】
続いて、図12に示すように、アドレス12から文字「A」を読み出し、この文字「A」をアドレス5に書き戻した後、読出しアドレスradr,書込みアドレスwadrとしてそれぞれアドレス13,6を指定する。
【0011】
このように、符号語(Copy Pointer,Match Count=4,Match Address=9)に基づき、辞書からデータを1文字(単位データ)ずつ読み出し、読み出した文字を辞書の別のアドレスに書き戻した後、次の1文字を読み出すことにより、文字列「ABCA」を復号する。
【0012】
従来、このLZ77法を採用して圧縮したデータを復号するデコーダ回路では、読み出した単位データを、動作クロックの1周期で辞書に書き戻すようになっていた。
【0013】
【特許文献1】国際公開番号W02003/032296の再公表特許公報(第12〜13頁、第3図、第4図)
【発明の開示】
【発明が解決しようとする課題】
【0014】
しかし、この従来のデコーダ回路は、次のような理由から、復号処理を高速化するのに不向きであった。すなわち、例えば0.11μmCMOSプロセスを採用したASIC(特定用途向けLSI)上でデコーダ回路を設計し、このASIC上のSRAMに辞書を格納するようにした場合、辞書が512バイト,1024バイトまたは2048バイトのような大きなサイズであると、SRAMに対してデータの読出し及び書戻しを行うのに2ナノ秒程度の時間がかかる。この動作は、例えばフリップ・フロップが0.3ナノ秒程度で動作するのと比較して低速である。
【0015】
さらに、このようにサイズの大きい辞書を格納するSRAMは、LSIチップ上で占める面積が大きくなり、コントローラの近くに配置することが困難になるので、コントローラとの間の配線が長くなる。このことも、SRAMの動作速度の低下につながる。
【0016】
このようにSRAMの動作が低速であることから、辞書から読み出したデータを1クロック周期で辞書に書き戻すようにすると、クロック周期を長くとらなければならない。そのため、高速化に不向きであった。
【0017】
本発明は、上述の点に鑑み、LZ77法を採用して圧縮したデータを復号するデコーダ回路のように、辞書からデータを単位データずつ読み出し、読み出した単位データを辞書の別のアドレスに書き戻した後、次の単位データを読み出すことによってデータを復号するデコーダ回路において、復号処理の高速化を実現することを課題としてなされたものである。
【課題を解決するための手段】
【0018】
この課題を解決するために、本発明に係るデコーダ回路は、メモリに格納された辞書から所定の単位データずつデータを読み出し、読み出した単位データをこの辞書の別のアドレスに書き戻した後、次の単位データを読み出すことによってデータを復号するデコーダ回路において、この辞書から読み出された単位データを遅延させる第1の遅延手段と、データを選択する選択手段と、この選択手段によって選択されたデータを遅延させる第2の遅延手段とを備え、この辞書には、この第2の遅延手段からの遅延データが書き戻され、この選択手段は、この第1の遅延手段からの遅延データとこの第2の遅延手段からの遅延データとが供給され、この辞書の書込みアドレスと読出しアドレスとがこれらの第1及び第2の遅延手段での遅延量に応じた所定の近さの範囲内にある場合にはこの第2の遅延手段からの遅延データを選択し、それ以外の場合にはこの第1の遅延手段からの遅延データを選択することを特徴とする。
【0019】
このデコーダ回路では、辞書から読み出された単位データが、第1の遅延手段によって遅延されて、選択手段に供給される。また、この選択手段で選択されたデータが、第2の遅延手段によって遅延されて、辞書に書き戻されるとともに選択手段に供給される。
【0020】
辞書から読み出されたデータが辞書に書き戻されるタイミングが第1及び第2の遅延手段での遅延量分遅れる関係で、辞書の書込みアドレスの近傍のアドレスが読出しアドレスとして指定されている場合には、その読出しアドレスから単位データを読み出した後、その読み出したデータを書き戻す前に、その読出しアドレスのデータが書き換わる(先に読み出したデータがその読み出しアドレスに書き戻される)可能性がある。
【0021】
そして、このようにデータが書き換わるときには、その読出しアドレスから読み出したデータではなく、この書き換わる新しいデータのほうを書き戻さなければ、辞書を正確に復元することができない。
【0022】
そこで、選択手段では、辞書の書込みアドレスと読出しアドレスとが第1及び第2の遅延手段での遅延量に応じた所定の近さの範囲内にある場合(すなわち、書込みアドレスの近傍が読出しアドレスとして指定されており、その読出しアドレスのデータが書き換わる可能性がある場合)には、第2の遅延手段からの遅延データが選択される。その結果、辞書から読み出されたデータが、第2の遅延手段からの遅延データにすり替えられて、辞書に書き戻される。
【0023】
この第2の遅延手段からの遅延データは、先に辞書から読み出したデータ、すなわち、その読出しアドレスに書き戻されるデータ(書き換わる新しいデータ)である。これにより、書き換わる新しいデータのほうが書き戻されるので、辞書が正確に復元される。
【0024】
他方、それ以外の場合には、選択手段では、第1の遅延手段からの遅延データが選択される。その結果、辞書から読み出されたデータが、単に第1及び第2の遅延手段によって遅延された後、辞書に書き戻される。
【0025】
このように、このデコーダ回路によれば、辞書から読み出したデータを遅延させて辞書に書き戻し、且つ、書込みアドレスの近傍が読出しアドレスとして指定されている場合にも、辞書を正確に復元することができる。
【0026】
そして、辞書から読み出されたデータを第1の遅延手段によって遅延させて選択手段に供給するので、辞書を格納したメモリの動作が低速であっても、第1の遅延手段でタイミングマージンをとることができる。その結果、選択手段には高速にデータを供給することができるので、選択手段から高速にデータを出力させることができる。これにより、パイプライン処理による復号処理の高速化を実現することができる。
【0027】
次に、本発明に係るデコード方法は、メモリに格納された辞書から所定の単位データずつデータを読み出し、読み出した単位データをこの辞書の別のアドレスに書き戻した後、次の単位データを読み出すことによってデータを復号するデコード方法において、この辞書から読み出された単位データを遅延させる第1のステップと、データを選択する第2のステップと、この第2のステップによって選択されたデータを遅延させてこの辞書に書き戻す第3のステップとを有し、この第2のステップでは、この第1のステップによる遅延データとこの第3のステップによる遅延データとのうち、この辞書の書込みアドレスと読出しアドレスとがこの第1及び第3のステップによる遅延量に応じた所定の近さの範囲内にある場合には第3のステップによる遅延データを選択し、それ以外の場合には第1のステップによる遅延データを選択することを特徴とする。
【0028】
この文字列検索方法によれば、前述の、本発明に係るデコーダ回路について述べたのと全く同様にして、書込みアドレスの近傍が読出しアドレスとして指定されている場合にも辞書を正確に復元しつつ、パイプライン処理による復号処理の高速化を実現することができる。
【発明の効果】
【0029】
本発明によれば、メモリに格納された辞書から所定の単位データずつデータを読み出し、読み出した単位データをこの辞書の別のアドレスに書き戻した後、次の単位データを読み出すことによってデータを復号するデコーダ回路において、書込みアドレスの近傍が読出しアドレスとして指定されている場合にも辞書を正確に復元しつつ、パイプライン処理による復号処理の高速化を実現することができるという効果が得られる。
【発明を実施するための最良の形態】
【0030】
以下、LZ77法を採用して圧縮したデータを復号するデコーダ回路に本発明を適用した例について、図面を用いて具体的に説明する。
【0031】
最初に、辞書から読み出した文字をフリップ・フロップによって動作クロックの2周期分遅延させて辞書に書き戻し、且つ、書込みアドレスの近傍が読出しアドレスとして指定されている場合に、辞書から読み出されたデータをフリップ・フロップのデータですり替えるアルゴリズムについて説明する。
【0032】
図1は、こうしたアルゴリズムを採用したデコーダ回路の構成を示すブロック図である。このデコーダ回路には、組み合わせ論理回路1と、8ビットのレジスタ2及び3とが設けられている。レジスタ2,3は、それぞれ8個のD型フリップ・フロップを並列に配置することによって構成されている。
【0033】
SRAM4には、図8に例示したような辞書(ヒストリ・バッファ)が格納されている。図示しないコントローラからは、読出しアドレスradrと、書込みアドレスwadrと、現在のクロック周期についての書込みイネーブル信号wenとが供給される。
【0034】
この辞書からは、書込みイネーブル信号wenが‘1’となったクロック周期に、読出しアドレスradrとして指定されたアドレスから、図8に例示したようにして文字(1バイトのデータ)が読み出される。辞書から読み出されたこのデータhbdatは、組み合わせ論理回路1に供給される。
【0035】
組み合わせ論理回路1には、後述するレジスタ2の出力next_wdat及びレジスタ3の出力wdatも供給される。
【0036】
また、前述のコントローラからは、この組み合わせ論理回路1に、読出しアドレスradrと、書込みアドレスwadrと、書込みイネーブル信号wenと、次のクロック周期についての書込みイネーブル信号next_wenとが供給される。
【0037】
組み合わせ論理回路1は、読出しアドレスradr,書込みアドレスwadr,書込みイネーブル信号next_wen及びwenの内容に基づき、辞書から読み出されたデータhbdatと、レジスタ2の出力next_wdatと、レジスタ3の出力wdatとのうちのいずれか1つを、辞書から読み出したデータrdatとして選択して出力する回路である。
【0038】
図2は、この組み合わせ論理回路1の構成をハードウェア回路として描いたブロック図である。3入力1出力のマルチプレクサ5と、2入力1出力のマルチプレクサ6と、3入力1出力のマルチプレクサ7とが設けられている。
【0039】
マルチプレクサ5の入力端S1,S2,S3には、wdat,next_wdat,hbdatがそれぞれ供給される。マルチプレクサ5の選択制御端子C1,C2には、それぞれwen,next_wenが供給される。
【0040】
マルチプレクサ5は、wen=‘1’の場合には、入力端S1に供給されたwdatを選択して出力端Dから出力し、wen=‘0’であるがnext_wen=‘1’の場合には、入力端S2に供給されたnext_wdatを選択して出力端Dから出力し、それ以外の場合には、入力端S3に供給されたhbdatを選択して出力端Dから出力する。
【0041】
マルチプレクサ6の入力端S1,S2には、next_wdat,hbdatがそれぞれ供給される。マルチプレクサ6の選択制御端子Cには、図示しないアンド回路から、wenとnext_wenとの論理積を示す信号が供給される。
【0042】
マルチプレクサ6は、wenとnext_wenとの論理積が‘1’の場合(現在のクロック周期,次のクロック周期の両方について書込みが許可されている場合)には、供給さ端S1に供給されたnext_wdatを選択して出力端Dから出力し、それ以外の場合には、入力端S2に供給されたhbdatを選択して出力端Dから出力する。
【0043】
マルチプレクサ7の入力端S1,S2,S3には、マルチプレクサ5の出力,マルチプレクサ6の出力,hbdatがそれぞれ供給される。マルチプレクサ7の選択制御端子C1,C2には、それぞれradr,wadrが供給される。
【0044】
マルチプレクサ7は、radrとwadrとが一致する場合には、入力端S1に供給されたマルチプレクサ5の出力を選択して出力端Dからrdatとして出力し、radrとwadr+1(書込みアドレスの次のアドレス)とが一致する場合には、入力端S2に供給されたマルチプレクサ6の出力を選択して出力端Dからrdatとして出力し、それ以外の場合には、入力端S3に供給されたhbdatを選択して出力端Dからrdatとして出力する。
【0045】
なお、図1の組み合わせ論理回路1のブロック内には、この組み合わせ論理回路1をASIC(特定用途向けLSI)やプログラマブル・ロジック・デバイス(FPGA等)として設計する場合のロジックを、ハードウェア記述言語の一種であるVerilog HDLを表記している。
【0046】
図1に示すように、組み合わせ論理回路1から出力されたデータrdatは、レジスタ2に供給される。レジスタ2からは、このデータrdatを1クロック周期遅延させたデータrdat_d(次のクロック周期に辞書に書き戻すデータであるnext_wdat)が出力される、このデータnext_wdatは、レジスタ3に供給されるとともに、前述のように組み合わせ論理回路1に供給される。
【0047】
レジスタ3からは、このデータnext_wdatを1クロック周期遅延させたデータwdat(現在のクロック周期に辞書に書き戻すデータ)が出力される、このデータwdatは、SRAM4に供給されるとともに、前述のように組み合わせ論理回路1に供給される。
【0048】
SRAM4内の辞書には、書込みイネーブル信号wenが‘1’となったクロック周期に、書込みアドレスwadrとして指定されたアドレスに、このデータwdatが書き込まれる。
【0049】
図3及び図4は、この図1のデコーダ回路において、辞書から読み出されたデータをフリップ・フロップ(レジスタ2またはレジスタ3)からの遅延データにすり替えて辞書に書き戻す場合を示す図である。
【0050】
辞書から読み出されたデータが辞書に書き戻されるタイミングがレジスタ2及び3での遅延量である2クロック周期分遅れる関係で、書込みアドレスwadrと同じアドレスが読出しアドレスradrとして指定されている場合や、書込みアドレスwadrの次のアドレスが読出しアドレスradrとして指定されている場合には、その読出しアドレスから文字を読み出した後、その読み出した文字を書き戻す前に、その読出しアドレスの文字が書き換わる(先に読み出した文字がその読み出しアドレスに書き戻される)可能性がある。
【0051】
そして、このようにデータが書き換わるときには、その読出しアドレスから読み出した文字ではなく、この書き換わる新しい文字のほうを書き戻さなければ、辞書を正確に復元することができない。
【0052】
図3は、書込みアドレスwadrと同じアドレスが読出しアドレスradrとして指定されている場合を例示している。この例の場合には、読出しアドレスradrとして指定されたアドレス2から文字「C」を読み出した後、その文字「C」を辞書に書き戻す前に、アドレス2の文字が書き換わる(先に読み出したアドレス0の文字「A」またはアドレス1の文字「B」がアドレス2に書き戻される)可能性がある。
【0053】
すなわち、現在のクロック周期についての書込みイネーブル信号wenが‘1’であれば、2クロック周期前に読み出したアドレス0の文字「A」がアドレス2に書き戻されるので、アドレス2の文字が「A」に書き換わる。したがって、この場合には、アドレス2から読み出した文字「C」ではなく、この書き換わる新しい文字「A」のほうを書き戻さなければ、辞書を正確に復元することができない。
【0054】
そして、この場合には、図1の組み合わせ論理回路1では、radrとwadrとが一致し、且つwen=‘1’であることから、レジスタ3の出力wdatが選択されてrdatとして出力される(図2のブロック図では、wen=‘1’であることからマルチプレクサ5でwdatが選択されてマルチプレクサ7に供給され、radrとwadrとが一致することからマルチプレクサ7でこのwdatが選択されてrdatとして出力される)。その結果、辞書から読み出されたデータhbdatが、レジスタ3の出力wdatにすり替えられて、辞書に書き戻される。
【0055】
レジスタ3の出力wdatは、2クロック周期前に図3の辞書のアドレス0から読み出した文字「A」であり、したがって、アドレス2に書き戻されるデータ(書き換わる新しい文字)である。これにより、書き換わる新しい文字「A」のほうが書き戻されるので、辞書が正確に復元される。
【0056】
また、図3の例において、書込みイネーブル信号wenは‘0’であるが次のクロック周期についての書込みイネーブル信号next_wenが‘1’であれば、1クロック周期前に読み出したアドレス1の文字「B」がアドレス2に書き戻されるので、アドレス2の文字が「B」に書き換わる。したがって、この場合には、アドレス2から読み出した文字「C」ではなく、この書き換わる新しい文字「B」のほうを書き戻さなければ、辞書を正確に復元することができない。
【0057】
そして、この場合には、図1の組み合わせ論理回路1では、radrとwadr+1とが一致し、且つnext_wen=‘1’であることから、レジスタ2の出力next_wdatが選択されてrdatとして出力される(図2のブロック図では、next_wen=‘1’であることからマルチプレクサ5でnext_wdatが選択されてマルチプレクサ7に供給され、radrとwadrとが一致することからマルチプレクサ7でこのnext_wdatが選択されてrdatとして出力される)。その結果、辞書から読み出されたデータhbdatが、レジスタ2の出力next_wdatにすり替えられて、辞書に書き戻される。
【0058】
レジスタ2の出力next_wdatは、1クロック周期前に図3の辞書のアドレス1から読み出した文字「B」であり、したがって、アドレス2に書き戻されるデータ(書き換わる新しい文字)である。これにより、書き換わる新しい文字「B」のほうが書き戻されるので、辞書が正確に復元される。
【0059】
他方、図4は、書込みアドレスwadrの次のアドレスが読出しアドレスradrとして指定されている場合を例示している。この例の場合には、読出しアドレスradrとして指定されたアドレス3から文字「C」を読み出した後、その文字「C」を辞書に書き戻す前に、アドレス3の文字が書き換わる(先に読み出したアドレス2の文字「C」がアドレス3に書き戻される)可能性がある。
【0060】
すなわち、現在のクロック周期についての書込みイネーブル信号wenが‘1’であり且つ次のクロック周期についての書込みイネーブル信号next_wenが‘1’であれば、2クロック周期前に読み出したアドレス1の文字「B」がアドレス2に書き戻されるとともに、1クロック周期前に読み出したアドレス2の文字「C」がアドレス3に書き戻される。この例の場合には偶然アドレス2とアドレス3とが同じ文字なのでアドレス3の文字は書き換わらないが、多くの場合にはアドレス3が別の文字に書き換わるので、その書き換わる新しい文字のほうを書き戻さなければ、辞書を正確に復元することができない。
【0061】
そして、この場合には、図1の組み合わせ論理回路1では、radrとwadr+1とが一致し、且つwenとnext_wenとの論理積が‘1’であることから、レジスタ2の出力next_wdatが選択されてrdatとして出力される(図2のブロック図では、wenとnext_wenとの論理積が‘1’であることからマルチプレクサ6でnext_wdatが選択されてマルチプレクサ7に供給され、radrとwadr+1とが一致することからマルチプレクサ7でこのnext_wdatが選択されてrdatとして出力される)。その結果、辞書から読み出されたデータhbdatが、レジスタ2の出力next_wdatにすり替えられて、辞書に書き戻される。
【0062】
レジスタ2の出力next_wdatは、1クロック周期前に図4の辞書のアドレス2から読み出した文字であり、したがって、アドレス3に書き戻される文字(多くの場合には、アドレス2とアドレス3とは別の文字なので、書き換わる新しい文字)である。これにより、書き換わる新しい文字のほうが書き戻されるので、辞書が正確に復元される。
【0063】
以上に図3,図4を用いて説明した3つの場合以外の場合には、図1の組み合わせ論理回路1では、辞書から読み出されたデータhbdatが選択されてrdatとして出力される(図2のブロック図では、マルチプレクサ7でhbdatが選択されてrdatとして出力される)。その結果、辞書から読み出されたデータhbdatが、単にレジスタ2及びレジスタ3によって2クロック周期分遅延された後、辞書に書き戻される。
【0064】
このように、図1のデコーダ回路によれば、辞書から読み出したデータを2クロック周期分遅延させて辞書に書き戻し、且つ、書込みアドレスwadrの近傍が読出しアドレスradrとして指定されている場合にも、辞書を正確に復元することができる。
【0065】
ただし、図1のデコーダ回路では、SRAM4の動作がフリップ・フロップ(レジスタ2やレジスタ3)と比較して低速であることから、SRAM4から組み合わせ論理回路1にデータhbdatを高速に供給することができない。そのため、組み合わせ論理回路1から高速にデータrdatを出力させることができないので、復号処理の高速化は困難である。
【0066】
そこで、本発明によるデコーダ回路は、図1のデコーダ回路におけるように、辞書から読み出されたデータをフリップ・フロップのデータですり替えるアルゴリズムを採用し、且つ、パイプライン処理を最適化するように構成されている。図5は、この本発明によるデコーダ回路の構成を示すブロック図である。このデコーダ回路のうち、レジスタ2,レジスタ3及びSRAM4は、図1に示したのと同一のものであり、重複説明を省略する。
【0067】
このデコーダ回路には、図1に示した組み合わせ論理回路1が設けられておらず、その代わりに、レジスタ2とレジスタ3との間に組み合わせ論理回路10が設けられている。
【0068】
辞書から読み出されたこのデータhbdatは、レジスタ2に供給される。レジスタ2からは、このデータhbdatを1クロック周期遅延させたデータhbdat_dが出力される、このデータhbdat_dは、組み合わせ論理回路10に供給される。
【0069】
組み合わせ論理回路10には、レジスタ3の出力wdatがそのまま供給されるとともに、レジスタ3の出力wdatをさらに1クロック周期遅延させたレジスタ9の出力wdat_dが供給される。
【0070】
また、読出しアドレスradrと、書込みアドレスwadrと、書込みイネーブル信号next_wen,wenをそれぞれ図示しないフリップ・フロップで1クロック周期遅延させたwen,wen_dとが組み合わせ論理回路10に供給される。
【0071】
組み合わせ論理回路10は、radr,wadr,wen及びwen_dの内容に基づき、データhbdat_dと、wdatと、wdat_dとのうちのいずれか1つを、辞書から読み出したデータrdat_dとして選択して出力する回路である。
【0072】
図6は、この組み合わせ論理回路10の構成をハードウェア回路として描いたブロック図である。3入力1出力のマルチプレクサ11と、2入力1出力のマルチプレクサ12と、3入力1出力のマルチプレクサ13とが設けられている。
【0073】
マルチプレクサ11の入力端S1,S2,S3には、wdat_d,wdat,hbdat_dがそれぞれ供給される。マルチプレクサ5の選択制御端子C1,C2には、それぞれwen_d,wenが供給される。
【0074】
マルチプレクサ11は、wen_d=‘1’の場合には、入力端S1に供給されたwdat_dを選択して出力端Dから出力し、wen_d=‘0’であるがwen=‘1’の場合には、入力端S2に供給されたwdatを選択して出力端Dから出力し、それ以外の場合には、入力端S3に供給されたhbdat_dを選択して出力端Dから出力する。
【0075】
マルチプレクサ12の入力端S1,S2には、wdat,hbdat_dがそれぞれ供給される。マルチプレクサ12の選択制御端子Cには、図示しないアンド回路から、wen_dとwenとの論理積を示す信号が供給される。
【0076】
マルチプレクサ12は、wen_dとwenとの論理積が‘1’の場合には、入力端S1に供給されたwdatを選択して出力端Dから出力し、それ以外の場合には、入力端S2に供給されたhbdat_dを選択して出力端Dから出力する。
【0077】
マルチプレクサ13の入力端S1,S2,S3には、マルチプレクサ11の出力,マルチプレクサ12の出力,hbdat_dがそれぞれ供給される。マルチプレクサ13の選択制御端子C1,C2には、それぞれradr,wadrが供給される。
【0078】
マルチプレクサ13は、radrとwadrとが一致する場合には、入力端S1に供給されたマルチプレクサ11の出力を選択して出力端Dからrdat_dとして出力し、radrとwadr+1(書込みアドレスの次のアドレス)とが一致する場合には、入力端S2に供給されたマルチプレクサ12の出力を選択して出力端Dからrdat_dとして出力し、それ以外の場合には、入力端S3に供給されたhbdat_dを選択して出力端Dからrdat_dとして出力する。
【0079】
なお、図5の組み合わせ論理回路10のブロック内には、この組み合わせ論理回路10をASIC(特定用途向けLSI)やプログラマブル・ロジック・デバイス(FPGA等)として設計する場合のロジックを、ハードウェア記述言語の一種であるVerilog HDLを表記している。
【0080】
図5に示すように、組み合わせ論理回路10から出力されたデータrdat_dは、レジスタ3に供給される。レジスタ3からは、このデータrdat_dを1クロック周期遅延させたデータwdat(現在のクロック周期に辞書に書き戻すデータ)が出力される、このデータwdatは、SRAM4に供給されるとともに、前述のように組み合わせ論理回路1及びレジスタ9に供給される。
【0081】
この図5のデコーダ回路によれば、図1のデコーダ回路について図3及び図4を用いて説明したのと全く同様にして、辞書から読み出したデータを2クロック周期分遅延させて辞書に書き戻し、且つ、書込みアドレスwadrの近傍が読出しアドレスradrとして指定されている場合(書込みアドレスwadrと同じアドレスまたは書込みアドレスwadrの次のアドレスが読出しアドレスradrとして指定されている場合)にも、辞書を正確に復元することができる。
【0082】
そして、辞書から読み出されたデータをレジスタ2によって1クロック周期分遅延させて組み合わせ論理回路10に供給するので、SRAM4の動作が低速であっても、レジスタ2でタイミングマージンをとることができる。その結果、組み合わせ論理回路10には高速にデータを供給することができるので、組み合わせ論理回路10から高速にデータrdat_dを出力させることができる。これにより、パイプライン処理による復号処理の高速化を実現することができる。
【0083】
なお、以上の例では、辞書から読み出した文字を2クロック周期分遅延させて辞書に書き戻し、且つ、書込みアドレスの近傍が読出しアドレスとして指定されている場合に、辞書から読み出されたデータをフリップ・フロップのデータですり替える例について説明した。しかし、これに限らず、辞書から読み出した文字を3クロック周期分以上遅延させて辞書に書き戻し、且つ、書込みアドレスの近傍が読出しアドレスとして指定されている場合に、辞書から読み出されたデータをフリップ・フロップのデータですり替えるようにしてもよい。
【0084】
また、以上の例では、LZ77法を採用して圧縮したデータを復号するデコーダ回路に本発明を適用した例について説明した。しかし、本発明は、これに限らず、メモリに格納された辞書から所定の単位データずつデータを読み出し、読み出した単位データをこの辞書の別のアドレスに書き戻した後、次の単位データを読み出すことによってデータを復号するようにしたあらゆるデコーダ回路において、復号処理の高速化のために適用することができる。
【図面の簡単な説明】
【0085】
【図1】辞書から読み出されたデータをフリップ・フロップのデータですり替えるデコーダ回路の構成を示すブロック図である。
【図2】図1の組み合わせ論理回路1ハードウェア構成を示すブロック図である。本発明を適用した文字列検索回路の構成を示すブロック図である。
【図3】図1のデコーダ回路において、辞書から読み出されたデータをフリップ・フロップですり替えて辞書に書き戻す場合を示す図である。図2の文字列検索回路をハードウェア記述言語を用いて表記した図である。
【図4】図1のデコーダ回路において、辞書から読み出されたデータをフリップ・フロップですり替えて辞書に書き戻す場合を示す図である。
【図5】本発明のデコーダ回路の構成を示すブロック図である。
【図6】図5の組み合わせ論理回路のハードウェア構成を示すブロック図である。
【図7】辞書を利用した文字列の圧縮の様子を例示する図である。
【図8】辞書を利用した文字列の復号の様子を例示する図である。
【図9】辞書を利用した文字列の復号の様子を例示する図である。
【図10】辞書を利用した文字列の復号の様子を例示する図である。
【図11】辞書を利用した文字列の復号の様子を例示する図である。
【図12】辞書を利用した文字列の復号の様子を例示する図である。
【符号の説明】
【0086】
1,10 組み合わせ論理回路
2,3,9 レジスタ
4 SRAM
5〜7,11〜13 マルチプレクサ
【技術分野】
【0001】
本発明は、例えばLZ77法を採用して圧縮したデータを復号するデコーダ回路に関し、特に、復号処理の高速化を図ったものに関する。
【背景技術】
【0002】
辞書型のデータ圧縮アルゴリズムの一種として、LZ(Lempel-Ziv)77法が存在している。LZ77法は、例えばAITフォーマット,S−AITフォーマットまたはLTOフォーマットのテープドライブ内のALDC(Adaptive Lossless Data Compression)エンコーダ・ALDCデコーダなど、各種のデータ記録装置内のデータ圧縮・復号回路に採用されている(例えば、特許文献1参照。)。
【0003】
LZ77法の圧縮原理は、過去に入力された文字列(データ列)のうちの直近の所定サイズの文字列を辞書(ヒストリ・バッファ)に登録し、新たに入力された(すなわち、圧縮しようとする)文字列と一致する文字列をその辞書から検索して、当該新たに入力された文字列をその一致する文字列のアドレス情報で置き換えるというものである。この辞書は、静的なものではなく、圧縮が進むにつれて、今まさに圧縮しようとする文字列の直前の文字列を追加して古い文字列を除外するようにアップデートされるので、スライド辞書とも呼ばれる。
【0004】
図7は、この圧縮の様子を例示する図である。通常は辞書のサイズは512バイト,1024バイトまたは2048バイトであることが多いが、ここでは説明の都合上16バイトとしている。過去に入力された文字列のうちの直近の16文字の文字列「ABCCAB…BCC」(各文字A,B,Cは1バイト)が辞書として登録されている。16バイト前に入力された文字「A」にはアドレス0が付与されており、15バイト前に入力された文字「B」にはアドレス1が付与されており、1バイト前に入力された文字「C」にはアドレス15が付与されている。
【0005】
例えば、新たに入力された文字列が「ABCA」である場合には、検索の結果、辞書内のアドレス9〜12の文字列が「ABCA」と一致する。そこで、この場合には、検索結果を示す情報であるマッチアドレス(一致する文字列の最後のアドレスとして定義されるアドレス)として12を出力する。そして、最終的には、この文字列「ABCA」を、一致長4及び先頭アドレス9を示す符号語(Copy Pointer,Match Count=4,Match Address=9)に変換することにより、4バイトから2バイトに圧縮する。
【0006】
このようにして圧縮されたデータを復号するときには、逆に、この辞書を参照して、符号語(Copy Pointer,Match Count=4,Match Address=9)を文字列「ABCA」に変換する。その際、圧縮時の辞書のアップデートに対する逆の処理として、復号が進むにつれて、辞書の文字を書き換えることによって、圧縮時に使用した辞書を復元していく。
【0007】
図8〜図12は、この復号の様子を、図7に示した辞書と関連させて経時的に示す図である。まず、図8に示すように、読出しアドレスradrとして辞書のアドレス9(符号語が示すMatch Address=9)を指定するとともに、書込みアドレスwadrとして辞書のアドレス2を指定する。そして、図9に示すように、アドレス9から文字「A」を読み出し、この文字「A」をアドレス2に書き戻した後、読出しアドレスradr,書込みアドレスwadrとしてそれぞれアドレス10,3を指定する。
【0008】
続いて、図10に示すように、アドレス10から文字「B」を読み出し、この文字「B」をアドレス3に書き戻した後、読出しアドレスradr,書込みアドレスwadrとしてそれぞれアドレス11,4を指定する。
【0009】
続いて、図11に示すように、アドレス11から文字「C」を読み出し、この文字「C」をアドレス4に書き戻した後、読出しアドレスradr,書込みアドレスwadrとしてそれぞれアドレス12,5を指定する。
【0010】
続いて、図12に示すように、アドレス12から文字「A」を読み出し、この文字「A」をアドレス5に書き戻した後、読出しアドレスradr,書込みアドレスwadrとしてそれぞれアドレス13,6を指定する。
【0011】
このように、符号語(Copy Pointer,Match Count=4,Match Address=9)に基づき、辞書からデータを1文字(単位データ)ずつ読み出し、読み出した文字を辞書の別のアドレスに書き戻した後、次の1文字を読み出すことにより、文字列「ABCA」を復号する。
【0012】
従来、このLZ77法を採用して圧縮したデータを復号するデコーダ回路では、読み出した単位データを、動作クロックの1周期で辞書に書き戻すようになっていた。
【0013】
【特許文献1】国際公開番号W02003/032296の再公表特許公報(第12〜13頁、第3図、第4図)
【発明の開示】
【発明が解決しようとする課題】
【0014】
しかし、この従来のデコーダ回路は、次のような理由から、復号処理を高速化するのに不向きであった。すなわち、例えば0.11μmCMOSプロセスを採用したASIC(特定用途向けLSI)上でデコーダ回路を設計し、このASIC上のSRAMに辞書を格納するようにした場合、辞書が512バイト,1024バイトまたは2048バイトのような大きなサイズであると、SRAMに対してデータの読出し及び書戻しを行うのに2ナノ秒程度の時間がかかる。この動作は、例えばフリップ・フロップが0.3ナノ秒程度で動作するのと比較して低速である。
【0015】
さらに、このようにサイズの大きい辞書を格納するSRAMは、LSIチップ上で占める面積が大きくなり、コントローラの近くに配置することが困難になるので、コントローラとの間の配線が長くなる。このことも、SRAMの動作速度の低下につながる。
【0016】
このようにSRAMの動作が低速であることから、辞書から読み出したデータを1クロック周期で辞書に書き戻すようにすると、クロック周期を長くとらなければならない。そのため、高速化に不向きであった。
【0017】
本発明は、上述の点に鑑み、LZ77法を採用して圧縮したデータを復号するデコーダ回路のように、辞書からデータを単位データずつ読み出し、読み出した単位データを辞書の別のアドレスに書き戻した後、次の単位データを読み出すことによってデータを復号するデコーダ回路において、復号処理の高速化を実現することを課題としてなされたものである。
【課題を解決するための手段】
【0018】
この課題を解決するために、本発明に係るデコーダ回路は、メモリに格納された辞書から所定の単位データずつデータを読み出し、読み出した単位データをこの辞書の別のアドレスに書き戻した後、次の単位データを読み出すことによってデータを復号するデコーダ回路において、この辞書から読み出された単位データを遅延させる第1の遅延手段と、データを選択する選択手段と、この選択手段によって選択されたデータを遅延させる第2の遅延手段とを備え、この辞書には、この第2の遅延手段からの遅延データが書き戻され、この選択手段は、この第1の遅延手段からの遅延データとこの第2の遅延手段からの遅延データとが供給され、この辞書の書込みアドレスと読出しアドレスとがこれらの第1及び第2の遅延手段での遅延量に応じた所定の近さの範囲内にある場合にはこの第2の遅延手段からの遅延データを選択し、それ以外の場合にはこの第1の遅延手段からの遅延データを選択することを特徴とする。
【0019】
このデコーダ回路では、辞書から読み出された単位データが、第1の遅延手段によって遅延されて、選択手段に供給される。また、この選択手段で選択されたデータが、第2の遅延手段によって遅延されて、辞書に書き戻されるとともに選択手段に供給される。
【0020】
辞書から読み出されたデータが辞書に書き戻されるタイミングが第1及び第2の遅延手段での遅延量分遅れる関係で、辞書の書込みアドレスの近傍のアドレスが読出しアドレスとして指定されている場合には、その読出しアドレスから単位データを読み出した後、その読み出したデータを書き戻す前に、その読出しアドレスのデータが書き換わる(先に読み出したデータがその読み出しアドレスに書き戻される)可能性がある。
【0021】
そして、このようにデータが書き換わるときには、その読出しアドレスから読み出したデータではなく、この書き換わる新しいデータのほうを書き戻さなければ、辞書を正確に復元することができない。
【0022】
そこで、選択手段では、辞書の書込みアドレスと読出しアドレスとが第1及び第2の遅延手段での遅延量に応じた所定の近さの範囲内にある場合(すなわち、書込みアドレスの近傍が読出しアドレスとして指定されており、その読出しアドレスのデータが書き換わる可能性がある場合)には、第2の遅延手段からの遅延データが選択される。その結果、辞書から読み出されたデータが、第2の遅延手段からの遅延データにすり替えられて、辞書に書き戻される。
【0023】
この第2の遅延手段からの遅延データは、先に辞書から読み出したデータ、すなわち、その読出しアドレスに書き戻されるデータ(書き換わる新しいデータ)である。これにより、書き換わる新しいデータのほうが書き戻されるので、辞書が正確に復元される。
【0024】
他方、それ以外の場合には、選択手段では、第1の遅延手段からの遅延データが選択される。その結果、辞書から読み出されたデータが、単に第1及び第2の遅延手段によって遅延された後、辞書に書き戻される。
【0025】
このように、このデコーダ回路によれば、辞書から読み出したデータを遅延させて辞書に書き戻し、且つ、書込みアドレスの近傍が読出しアドレスとして指定されている場合にも、辞書を正確に復元することができる。
【0026】
そして、辞書から読み出されたデータを第1の遅延手段によって遅延させて選択手段に供給するので、辞書を格納したメモリの動作が低速であっても、第1の遅延手段でタイミングマージンをとることができる。その結果、選択手段には高速にデータを供給することができるので、選択手段から高速にデータを出力させることができる。これにより、パイプライン処理による復号処理の高速化を実現することができる。
【0027】
次に、本発明に係るデコード方法は、メモリに格納された辞書から所定の単位データずつデータを読み出し、読み出した単位データをこの辞書の別のアドレスに書き戻した後、次の単位データを読み出すことによってデータを復号するデコード方法において、この辞書から読み出された単位データを遅延させる第1のステップと、データを選択する第2のステップと、この第2のステップによって選択されたデータを遅延させてこの辞書に書き戻す第3のステップとを有し、この第2のステップでは、この第1のステップによる遅延データとこの第3のステップによる遅延データとのうち、この辞書の書込みアドレスと読出しアドレスとがこの第1及び第3のステップによる遅延量に応じた所定の近さの範囲内にある場合には第3のステップによる遅延データを選択し、それ以外の場合には第1のステップによる遅延データを選択することを特徴とする。
【0028】
この文字列検索方法によれば、前述の、本発明に係るデコーダ回路について述べたのと全く同様にして、書込みアドレスの近傍が読出しアドレスとして指定されている場合にも辞書を正確に復元しつつ、パイプライン処理による復号処理の高速化を実現することができる。
【発明の効果】
【0029】
本発明によれば、メモリに格納された辞書から所定の単位データずつデータを読み出し、読み出した単位データをこの辞書の別のアドレスに書き戻した後、次の単位データを読み出すことによってデータを復号するデコーダ回路において、書込みアドレスの近傍が読出しアドレスとして指定されている場合にも辞書を正確に復元しつつ、パイプライン処理による復号処理の高速化を実現することができるという効果が得られる。
【発明を実施するための最良の形態】
【0030】
以下、LZ77法を採用して圧縮したデータを復号するデコーダ回路に本発明を適用した例について、図面を用いて具体的に説明する。
【0031】
最初に、辞書から読み出した文字をフリップ・フロップによって動作クロックの2周期分遅延させて辞書に書き戻し、且つ、書込みアドレスの近傍が読出しアドレスとして指定されている場合に、辞書から読み出されたデータをフリップ・フロップのデータですり替えるアルゴリズムについて説明する。
【0032】
図1は、こうしたアルゴリズムを採用したデコーダ回路の構成を示すブロック図である。このデコーダ回路には、組み合わせ論理回路1と、8ビットのレジスタ2及び3とが設けられている。レジスタ2,3は、それぞれ8個のD型フリップ・フロップを並列に配置することによって構成されている。
【0033】
SRAM4には、図8に例示したような辞書(ヒストリ・バッファ)が格納されている。図示しないコントローラからは、読出しアドレスradrと、書込みアドレスwadrと、現在のクロック周期についての書込みイネーブル信号wenとが供給される。
【0034】
この辞書からは、書込みイネーブル信号wenが‘1’となったクロック周期に、読出しアドレスradrとして指定されたアドレスから、図8に例示したようにして文字(1バイトのデータ)が読み出される。辞書から読み出されたこのデータhbdatは、組み合わせ論理回路1に供給される。
【0035】
組み合わせ論理回路1には、後述するレジスタ2の出力next_wdat及びレジスタ3の出力wdatも供給される。
【0036】
また、前述のコントローラからは、この組み合わせ論理回路1に、読出しアドレスradrと、書込みアドレスwadrと、書込みイネーブル信号wenと、次のクロック周期についての書込みイネーブル信号next_wenとが供給される。
【0037】
組み合わせ論理回路1は、読出しアドレスradr,書込みアドレスwadr,書込みイネーブル信号next_wen及びwenの内容に基づき、辞書から読み出されたデータhbdatと、レジスタ2の出力next_wdatと、レジスタ3の出力wdatとのうちのいずれか1つを、辞書から読み出したデータrdatとして選択して出力する回路である。
【0038】
図2は、この組み合わせ論理回路1の構成をハードウェア回路として描いたブロック図である。3入力1出力のマルチプレクサ5と、2入力1出力のマルチプレクサ6と、3入力1出力のマルチプレクサ7とが設けられている。
【0039】
マルチプレクサ5の入力端S1,S2,S3には、wdat,next_wdat,hbdatがそれぞれ供給される。マルチプレクサ5の選択制御端子C1,C2には、それぞれwen,next_wenが供給される。
【0040】
マルチプレクサ5は、wen=‘1’の場合には、入力端S1に供給されたwdatを選択して出力端Dから出力し、wen=‘0’であるがnext_wen=‘1’の場合には、入力端S2に供給されたnext_wdatを選択して出力端Dから出力し、それ以外の場合には、入力端S3に供給されたhbdatを選択して出力端Dから出力する。
【0041】
マルチプレクサ6の入力端S1,S2には、next_wdat,hbdatがそれぞれ供給される。マルチプレクサ6の選択制御端子Cには、図示しないアンド回路から、wenとnext_wenとの論理積を示す信号が供給される。
【0042】
マルチプレクサ6は、wenとnext_wenとの論理積が‘1’の場合(現在のクロック周期,次のクロック周期の両方について書込みが許可されている場合)には、供給さ端S1に供給されたnext_wdatを選択して出力端Dから出力し、それ以外の場合には、入力端S2に供給されたhbdatを選択して出力端Dから出力する。
【0043】
マルチプレクサ7の入力端S1,S2,S3には、マルチプレクサ5の出力,マルチプレクサ6の出力,hbdatがそれぞれ供給される。マルチプレクサ7の選択制御端子C1,C2には、それぞれradr,wadrが供給される。
【0044】
マルチプレクサ7は、radrとwadrとが一致する場合には、入力端S1に供給されたマルチプレクサ5の出力を選択して出力端Dからrdatとして出力し、radrとwadr+1(書込みアドレスの次のアドレス)とが一致する場合には、入力端S2に供給されたマルチプレクサ6の出力を選択して出力端Dからrdatとして出力し、それ以外の場合には、入力端S3に供給されたhbdatを選択して出力端Dからrdatとして出力する。
【0045】
なお、図1の組み合わせ論理回路1のブロック内には、この組み合わせ論理回路1をASIC(特定用途向けLSI)やプログラマブル・ロジック・デバイス(FPGA等)として設計する場合のロジックを、ハードウェア記述言語の一種であるVerilog HDLを表記している。
【0046】
図1に示すように、組み合わせ論理回路1から出力されたデータrdatは、レジスタ2に供給される。レジスタ2からは、このデータrdatを1クロック周期遅延させたデータrdat_d(次のクロック周期に辞書に書き戻すデータであるnext_wdat)が出力される、このデータnext_wdatは、レジスタ3に供給されるとともに、前述のように組み合わせ論理回路1に供給される。
【0047】
レジスタ3からは、このデータnext_wdatを1クロック周期遅延させたデータwdat(現在のクロック周期に辞書に書き戻すデータ)が出力される、このデータwdatは、SRAM4に供給されるとともに、前述のように組み合わせ論理回路1に供給される。
【0048】
SRAM4内の辞書には、書込みイネーブル信号wenが‘1’となったクロック周期に、書込みアドレスwadrとして指定されたアドレスに、このデータwdatが書き込まれる。
【0049】
図3及び図4は、この図1のデコーダ回路において、辞書から読み出されたデータをフリップ・フロップ(レジスタ2またはレジスタ3)からの遅延データにすり替えて辞書に書き戻す場合を示す図である。
【0050】
辞書から読み出されたデータが辞書に書き戻されるタイミングがレジスタ2及び3での遅延量である2クロック周期分遅れる関係で、書込みアドレスwadrと同じアドレスが読出しアドレスradrとして指定されている場合や、書込みアドレスwadrの次のアドレスが読出しアドレスradrとして指定されている場合には、その読出しアドレスから文字を読み出した後、その読み出した文字を書き戻す前に、その読出しアドレスの文字が書き換わる(先に読み出した文字がその読み出しアドレスに書き戻される)可能性がある。
【0051】
そして、このようにデータが書き換わるときには、その読出しアドレスから読み出した文字ではなく、この書き換わる新しい文字のほうを書き戻さなければ、辞書を正確に復元することができない。
【0052】
図3は、書込みアドレスwadrと同じアドレスが読出しアドレスradrとして指定されている場合を例示している。この例の場合には、読出しアドレスradrとして指定されたアドレス2から文字「C」を読み出した後、その文字「C」を辞書に書き戻す前に、アドレス2の文字が書き換わる(先に読み出したアドレス0の文字「A」またはアドレス1の文字「B」がアドレス2に書き戻される)可能性がある。
【0053】
すなわち、現在のクロック周期についての書込みイネーブル信号wenが‘1’であれば、2クロック周期前に読み出したアドレス0の文字「A」がアドレス2に書き戻されるので、アドレス2の文字が「A」に書き換わる。したがって、この場合には、アドレス2から読み出した文字「C」ではなく、この書き換わる新しい文字「A」のほうを書き戻さなければ、辞書を正確に復元することができない。
【0054】
そして、この場合には、図1の組み合わせ論理回路1では、radrとwadrとが一致し、且つwen=‘1’であることから、レジスタ3の出力wdatが選択されてrdatとして出力される(図2のブロック図では、wen=‘1’であることからマルチプレクサ5でwdatが選択されてマルチプレクサ7に供給され、radrとwadrとが一致することからマルチプレクサ7でこのwdatが選択されてrdatとして出力される)。その結果、辞書から読み出されたデータhbdatが、レジスタ3の出力wdatにすり替えられて、辞書に書き戻される。
【0055】
レジスタ3の出力wdatは、2クロック周期前に図3の辞書のアドレス0から読み出した文字「A」であり、したがって、アドレス2に書き戻されるデータ(書き換わる新しい文字)である。これにより、書き換わる新しい文字「A」のほうが書き戻されるので、辞書が正確に復元される。
【0056】
また、図3の例において、書込みイネーブル信号wenは‘0’であるが次のクロック周期についての書込みイネーブル信号next_wenが‘1’であれば、1クロック周期前に読み出したアドレス1の文字「B」がアドレス2に書き戻されるので、アドレス2の文字が「B」に書き換わる。したがって、この場合には、アドレス2から読み出した文字「C」ではなく、この書き換わる新しい文字「B」のほうを書き戻さなければ、辞書を正確に復元することができない。
【0057】
そして、この場合には、図1の組み合わせ論理回路1では、radrとwadr+1とが一致し、且つnext_wen=‘1’であることから、レジスタ2の出力next_wdatが選択されてrdatとして出力される(図2のブロック図では、next_wen=‘1’であることからマルチプレクサ5でnext_wdatが選択されてマルチプレクサ7に供給され、radrとwadrとが一致することからマルチプレクサ7でこのnext_wdatが選択されてrdatとして出力される)。その結果、辞書から読み出されたデータhbdatが、レジスタ2の出力next_wdatにすり替えられて、辞書に書き戻される。
【0058】
レジスタ2の出力next_wdatは、1クロック周期前に図3の辞書のアドレス1から読み出した文字「B」であり、したがって、アドレス2に書き戻されるデータ(書き換わる新しい文字)である。これにより、書き換わる新しい文字「B」のほうが書き戻されるので、辞書が正確に復元される。
【0059】
他方、図4は、書込みアドレスwadrの次のアドレスが読出しアドレスradrとして指定されている場合を例示している。この例の場合には、読出しアドレスradrとして指定されたアドレス3から文字「C」を読み出した後、その文字「C」を辞書に書き戻す前に、アドレス3の文字が書き換わる(先に読み出したアドレス2の文字「C」がアドレス3に書き戻される)可能性がある。
【0060】
すなわち、現在のクロック周期についての書込みイネーブル信号wenが‘1’であり且つ次のクロック周期についての書込みイネーブル信号next_wenが‘1’であれば、2クロック周期前に読み出したアドレス1の文字「B」がアドレス2に書き戻されるとともに、1クロック周期前に読み出したアドレス2の文字「C」がアドレス3に書き戻される。この例の場合には偶然アドレス2とアドレス3とが同じ文字なのでアドレス3の文字は書き換わらないが、多くの場合にはアドレス3が別の文字に書き換わるので、その書き換わる新しい文字のほうを書き戻さなければ、辞書を正確に復元することができない。
【0061】
そして、この場合には、図1の組み合わせ論理回路1では、radrとwadr+1とが一致し、且つwenとnext_wenとの論理積が‘1’であることから、レジスタ2の出力next_wdatが選択されてrdatとして出力される(図2のブロック図では、wenとnext_wenとの論理積が‘1’であることからマルチプレクサ6でnext_wdatが選択されてマルチプレクサ7に供給され、radrとwadr+1とが一致することからマルチプレクサ7でこのnext_wdatが選択されてrdatとして出力される)。その結果、辞書から読み出されたデータhbdatが、レジスタ2の出力next_wdatにすり替えられて、辞書に書き戻される。
【0062】
レジスタ2の出力next_wdatは、1クロック周期前に図4の辞書のアドレス2から読み出した文字であり、したがって、アドレス3に書き戻される文字(多くの場合には、アドレス2とアドレス3とは別の文字なので、書き換わる新しい文字)である。これにより、書き換わる新しい文字のほうが書き戻されるので、辞書が正確に復元される。
【0063】
以上に図3,図4を用いて説明した3つの場合以外の場合には、図1の組み合わせ論理回路1では、辞書から読み出されたデータhbdatが選択されてrdatとして出力される(図2のブロック図では、マルチプレクサ7でhbdatが選択されてrdatとして出力される)。その結果、辞書から読み出されたデータhbdatが、単にレジスタ2及びレジスタ3によって2クロック周期分遅延された後、辞書に書き戻される。
【0064】
このように、図1のデコーダ回路によれば、辞書から読み出したデータを2クロック周期分遅延させて辞書に書き戻し、且つ、書込みアドレスwadrの近傍が読出しアドレスradrとして指定されている場合にも、辞書を正確に復元することができる。
【0065】
ただし、図1のデコーダ回路では、SRAM4の動作がフリップ・フロップ(レジスタ2やレジスタ3)と比較して低速であることから、SRAM4から組み合わせ論理回路1にデータhbdatを高速に供給することができない。そのため、組み合わせ論理回路1から高速にデータrdatを出力させることができないので、復号処理の高速化は困難である。
【0066】
そこで、本発明によるデコーダ回路は、図1のデコーダ回路におけるように、辞書から読み出されたデータをフリップ・フロップのデータですり替えるアルゴリズムを採用し、且つ、パイプライン処理を最適化するように構成されている。図5は、この本発明によるデコーダ回路の構成を示すブロック図である。このデコーダ回路のうち、レジスタ2,レジスタ3及びSRAM4は、図1に示したのと同一のものであり、重複説明を省略する。
【0067】
このデコーダ回路には、図1に示した組み合わせ論理回路1が設けられておらず、その代わりに、レジスタ2とレジスタ3との間に組み合わせ論理回路10が設けられている。
【0068】
辞書から読み出されたこのデータhbdatは、レジスタ2に供給される。レジスタ2からは、このデータhbdatを1クロック周期遅延させたデータhbdat_dが出力される、このデータhbdat_dは、組み合わせ論理回路10に供給される。
【0069】
組み合わせ論理回路10には、レジスタ3の出力wdatがそのまま供給されるとともに、レジスタ3の出力wdatをさらに1クロック周期遅延させたレジスタ9の出力wdat_dが供給される。
【0070】
また、読出しアドレスradrと、書込みアドレスwadrと、書込みイネーブル信号next_wen,wenをそれぞれ図示しないフリップ・フロップで1クロック周期遅延させたwen,wen_dとが組み合わせ論理回路10に供給される。
【0071】
組み合わせ論理回路10は、radr,wadr,wen及びwen_dの内容に基づき、データhbdat_dと、wdatと、wdat_dとのうちのいずれか1つを、辞書から読み出したデータrdat_dとして選択して出力する回路である。
【0072】
図6は、この組み合わせ論理回路10の構成をハードウェア回路として描いたブロック図である。3入力1出力のマルチプレクサ11と、2入力1出力のマルチプレクサ12と、3入力1出力のマルチプレクサ13とが設けられている。
【0073】
マルチプレクサ11の入力端S1,S2,S3には、wdat_d,wdat,hbdat_dがそれぞれ供給される。マルチプレクサ5の選択制御端子C1,C2には、それぞれwen_d,wenが供給される。
【0074】
マルチプレクサ11は、wen_d=‘1’の場合には、入力端S1に供給されたwdat_dを選択して出力端Dから出力し、wen_d=‘0’であるがwen=‘1’の場合には、入力端S2に供給されたwdatを選択して出力端Dから出力し、それ以外の場合には、入力端S3に供給されたhbdat_dを選択して出力端Dから出力する。
【0075】
マルチプレクサ12の入力端S1,S2には、wdat,hbdat_dがそれぞれ供給される。マルチプレクサ12の選択制御端子Cには、図示しないアンド回路から、wen_dとwenとの論理積を示す信号が供給される。
【0076】
マルチプレクサ12は、wen_dとwenとの論理積が‘1’の場合には、入力端S1に供給されたwdatを選択して出力端Dから出力し、それ以外の場合には、入力端S2に供給されたhbdat_dを選択して出力端Dから出力する。
【0077】
マルチプレクサ13の入力端S1,S2,S3には、マルチプレクサ11の出力,マルチプレクサ12の出力,hbdat_dがそれぞれ供給される。マルチプレクサ13の選択制御端子C1,C2には、それぞれradr,wadrが供給される。
【0078】
マルチプレクサ13は、radrとwadrとが一致する場合には、入力端S1に供給されたマルチプレクサ11の出力を選択して出力端Dからrdat_dとして出力し、radrとwadr+1(書込みアドレスの次のアドレス)とが一致する場合には、入力端S2に供給されたマルチプレクサ12の出力を選択して出力端Dからrdat_dとして出力し、それ以外の場合には、入力端S3に供給されたhbdat_dを選択して出力端Dからrdat_dとして出力する。
【0079】
なお、図5の組み合わせ論理回路10のブロック内には、この組み合わせ論理回路10をASIC(特定用途向けLSI)やプログラマブル・ロジック・デバイス(FPGA等)として設計する場合のロジックを、ハードウェア記述言語の一種であるVerilog HDLを表記している。
【0080】
図5に示すように、組み合わせ論理回路10から出力されたデータrdat_dは、レジスタ3に供給される。レジスタ3からは、このデータrdat_dを1クロック周期遅延させたデータwdat(現在のクロック周期に辞書に書き戻すデータ)が出力される、このデータwdatは、SRAM4に供給されるとともに、前述のように組み合わせ論理回路1及びレジスタ9に供給される。
【0081】
この図5のデコーダ回路によれば、図1のデコーダ回路について図3及び図4を用いて説明したのと全く同様にして、辞書から読み出したデータを2クロック周期分遅延させて辞書に書き戻し、且つ、書込みアドレスwadrの近傍が読出しアドレスradrとして指定されている場合(書込みアドレスwadrと同じアドレスまたは書込みアドレスwadrの次のアドレスが読出しアドレスradrとして指定されている場合)にも、辞書を正確に復元することができる。
【0082】
そして、辞書から読み出されたデータをレジスタ2によって1クロック周期分遅延させて組み合わせ論理回路10に供給するので、SRAM4の動作が低速であっても、レジスタ2でタイミングマージンをとることができる。その結果、組み合わせ論理回路10には高速にデータを供給することができるので、組み合わせ論理回路10から高速にデータrdat_dを出力させることができる。これにより、パイプライン処理による復号処理の高速化を実現することができる。
【0083】
なお、以上の例では、辞書から読み出した文字を2クロック周期分遅延させて辞書に書き戻し、且つ、書込みアドレスの近傍が読出しアドレスとして指定されている場合に、辞書から読み出されたデータをフリップ・フロップのデータですり替える例について説明した。しかし、これに限らず、辞書から読み出した文字を3クロック周期分以上遅延させて辞書に書き戻し、且つ、書込みアドレスの近傍が読出しアドレスとして指定されている場合に、辞書から読み出されたデータをフリップ・フロップのデータですり替えるようにしてもよい。
【0084】
また、以上の例では、LZ77法を採用して圧縮したデータを復号するデコーダ回路に本発明を適用した例について説明した。しかし、本発明は、これに限らず、メモリに格納された辞書から所定の単位データずつデータを読み出し、読み出した単位データをこの辞書の別のアドレスに書き戻した後、次の単位データを読み出すことによってデータを復号するようにしたあらゆるデコーダ回路において、復号処理の高速化のために適用することができる。
【図面の簡単な説明】
【0085】
【図1】辞書から読み出されたデータをフリップ・フロップのデータですり替えるデコーダ回路の構成を示すブロック図である。
【図2】図1の組み合わせ論理回路1ハードウェア構成を示すブロック図である。本発明を適用した文字列検索回路の構成を示すブロック図である。
【図3】図1のデコーダ回路において、辞書から読み出されたデータをフリップ・フロップですり替えて辞書に書き戻す場合を示す図である。図2の文字列検索回路をハードウェア記述言語を用いて表記した図である。
【図4】図1のデコーダ回路において、辞書から読み出されたデータをフリップ・フロップですり替えて辞書に書き戻す場合を示す図である。
【図5】本発明のデコーダ回路の構成を示すブロック図である。
【図6】図5の組み合わせ論理回路のハードウェア構成を示すブロック図である。
【図7】辞書を利用した文字列の圧縮の様子を例示する図である。
【図8】辞書を利用した文字列の復号の様子を例示する図である。
【図9】辞書を利用した文字列の復号の様子を例示する図である。
【図10】辞書を利用した文字列の復号の様子を例示する図である。
【図11】辞書を利用した文字列の復号の様子を例示する図である。
【図12】辞書を利用した文字列の復号の様子を例示する図である。
【符号の説明】
【0086】
1,10 組み合わせ論理回路
2,3,9 レジスタ
4 SRAM
5〜7,11〜13 マルチプレクサ
【特許請求の範囲】
【請求項1】
メモリに格納された辞書から所定の単位データずつデータを読み出し、読み出した前記単位データを前記辞書の別のアドレスに書き戻した後、次の前記単位データを読み出すことによってデータを復号するデコーダ回路において、
前記辞書から読み出された前記単位データを遅延させる第1の遅延手段と、
データを選択する選択手段と、
前記選択手段によって選択されたデータを遅延させる第2の遅延手段と
を備え、
前記辞書には、前記第2の遅延手段からの遅延データが書き戻され、
前記選択手段は、前記第1の遅延手段からの遅延データと前記第2の遅延手段からの遅延データとが供給され、前記辞書の書込みアドレスと読出しアドレスとが前記第1の遅延手段及び前記第2の遅延手段での遅延量に応じた所定の近さの範囲内にある場合には前記第2の遅延手段からの遅延データを選択し、それ以外の場合には前記第1の遅延手段からの遅延データを選択する
ことを特徴とするデコーダ回路。
【請求項2】
請求項1に記載のデコーダ回路において、
前記第1の遅延手段,前記第2の遅延手段は、それぞれデータを動作クロックの1周期分遅延させ、
前記選択手段は、前記書込みアドレスと前記読出しアドレスとが同じアドレスであるか、または前記書込みアドレスの次のアドレスと前記読出しアドレスとが同じである場合に、前記第2の遅延手段からの遅延データを選択し、それ以外の場合には前記第1の遅延手段からの遅延データを選択する
ことを特徴とするデコーダ回路。
【請求項3】
請求項2に記載のデコーダ回路において、前記第2の遅延手段からの遅延データがそのまま前記選択手段に供給されるとともに、第3の遅延手段によってさらに前記動作クロックの1周期分遅延されて前記選択手段に供給され、
前記選択手段は、
前記書込みアドレスと前記読出しアドレスとが同じアドレスである場合に、現在の書込みアドレスへのデータの書込みを許可する書込みイネーブル信号が供給されていれば、前記第2の遅延手段からそのまま供給される遅延データを選択し、現在の書込みアドレスの次のアドレスへのデータの書込みを許可する書込みイネーブル信号が供給されていれば、前記第3の遅延手段からの遅延データを選択し、
前記書込みアドレスの次のアドレスと前記読出しアドレスとが同じである場合に、現在の書込みアドレス及びその次のアドレスの両方へのデータの書込みを許可する書込みイネーブル信号が供給されていれば、前記第2の遅延手段からそのまま供給される遅延データを選択する
ことを特徴とするデコーダ回路。
【請求項4】
メモリに格納された辞書から所定の単位データずつデータを読み出し、読み出した前記単位データを前記辞書の別のアドレスに書き戻した後、次の前記単位データを読み出すことによってデータを復号するデコード方法において、
前記辞書から読み出された前記単位データを遅延させる第1のステップと、
データを選択する第2のステップと、
前記第2のステップによって選択されたデータを遅延させて前記辞書に書き戻す第3のステップと
を有し、
前記第2のステップでは、前記第1のステップによる遅延データと前記第3のステップによる遅延データとのうち、前記辞書の書込みアドレスと読出しアドレスとが前記第1のステップ及び前記第3のステップによる遅延量に応じた所定の近さの範囲内にある場合には前記第3のステップによる遅延データを選択し、それ以外の場合には前記第1のステップによる遅延データを選択する
ことを特徴とするデコード方法。
【請求項1】
メモリに格納された辞書から所定の単位データずつデータを読み出し、読み出した前記単位データを前記辞書の別のアドレスに書き戻した後、次の前記単位データを読み出すことによってデータを復号するデコーダ回路において、
前記辞書から読み出された前記単位データを遅延させる第1の遅延手段と、
データを選択する選択手段と、
前記選択手段によって選択されたデータを遅延させる第2の遅延手段と
を備え、
前記辞書には、前記第2の遅延手段からの遅延データが書き戻され、
前記選択手段は、前記第1の遅延手段からの遅延データと前記第2の遅延手段からの遅延データとが供給され、前記辞書の書込みアドレスと読出しアドレスとが前記第1の遅延手段及び前記第2の遅延手段での遅延量に応じた所定の近さの範囲内にある場合には前記第2の遅延手段からの遅延データを選択し、それ以外の場合には前記第1の遅延手段からの遅延データを選択する
ことを特徴とするデコーダ回路。
【請求項2】
請求項1に記載のデコーダ回路において、
前記第1の遅延手段,前記第2の遅延手段は、それぞれデータを動作クロックの1周期分遅延させ、
前記選択手段は、前記書込みアドレスと前記読出しアドレスとが同じアドレスであるか、または前記書込みアドレスの次のアドレスと前記読出しアドレスとが同じである場合に、前記第2の遅延手段からの遅延データを選択し、それ以外の場合には前記第1の遅延手段からの遅延データを選択する
ことを特徴とするデコーダ回路。
【請求項3】
請求項2に記載のデコーダ回路において、前記第2の遅延手段からの遅延データがそのまま前記選択手段に供給されるとともに、第3の遅延手段によってさらに前記動作クロックの1周期分遅延されて前記選択手段に供給され、
前記選択手段は、
前記書込みアドレスと前記読出しアドレスとが同じアドレスである場合に、現在の書込みアドレスへのデータの書込みを許可する書込みイネーブル信号が供給されていれば、前記第2の遅延手段からそのまま供給される遅延データを選択し、現在の書込みアドレスの次のアドレスへのデータの書込みを許可する書込みイネーブル信号が供給されていれば、前記第3の遅延手段からの遅延データを選択し、
前記書込みアドレスの次のアドレスと前記読出しアドレスとが同じである場合に、現在の書込みアドレス及びその次のアドレスの両方へのデータの書込みを許可する書込みイネーブル信号が供給されていれば、前記第2の遅延手段からそのまま供給される遅延データを選択する
ことを特徴とするデコーダ回路。
【請求項4】
メモリに格納された辞書から所定の単位データずつデータを読み出し、読み出した前記単位データを前記辞書の別のアドレスに書き戻した後、次の前記単位データを読み出すことによってデータを復号するデコード方法において、
前記辞書から読み出された前記単位データを遅延させる第1のステップと、
データを選択する第2のステップと、
前記第2のステップによって選択されたデータを遅延させて前記辞書に書き戻す第3のステップと
を有し、
前記第2のステップでは、前記第1のステップによる遅延データと前記第3のステップによる遅延データとのうち、前記辞書の書込みアドレスと読出しアドレスとが前記第1のステップ及び前記第3のステップによる遅延量に応じた所定の近さの範囲内にある場合には前記第3のステップによる遅延データを選択し、それ以外の場合には前記第1のステップによる遅延データを選択する
ことを特徴とするデコード方法。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【公開番号】特開2006−332982(P2006−332982A)
【公開日】平成18年12月7日(2006.12.7)
【国際特許分類】
【出願番号】特願2005−152685(P2005−152685)
【出願日】平成17年5月25日(2005.5.25)
【出願人】(000002185)ソニー株式会社 (34,172)
【Fターム(参考)】
【公開日】平成18年12月7日(2006.12.7)
【国際特許分類】
【出願日】平成17年5月25日(2005.5.25)
【出願人】(000002185)ソニー株式会社 (34,172)
【Fターム(参考)】
[ Back to top ]