JPH089371A - 並列処理パターンマッチングを用いた可変長さ符号の高速再同期方法 - Google Patents
並列処理パターンマッチングを用いた可変長さ符号の高速再同期方法Info
- Publication number
- JPH089371A JPH089371A JP4091495A JP4091495A JPH089371A JP H089371 A JPH089371 A JP H089371A JP 4091495 A JP4091495 A JP 4091495A JP 4091495 A JP4091495 A JP 4091495A JP H089371 A JPH089371 A JP H089371A
- Authority
- JP
- Japan
- Prior art keywords
- bit string
- input bit
- pattern
- input
- matches
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
- 238000012545 processing Methods 0.000 title claims abstract description 38
- 238000000034 method Methods 0.000 title claims description 26
- 230000005540 biological transmission Effects 0.000 claims abstract description 27
- 230000001360 synchronised effect Effects 0.000 claims 3
- 208000034530 PLAA-associated neurodevelopmental disease Diseases 0.000 claims 1
- 238000001514 detection method Methods 0.000 claims 1
- 238000005530 etching Methods 0.000 claims 1
- 238000010586 diagram Methods 0.000 description 8
- 101000585266 Tropidechis carinatus Acidic phospholipase A2 3 Proteins 0.000 description 3
- 101000585299 Tropidechis carinatus Acidic phospholipase A2 2 Proteins 0.000 description 2
- 101000572976 Homo sapiens POU domain, class 2, transcription factor 3 Proteins 0.000 description 1
- 241000353097 Molva molva Species 0.000 description 1
- 102100026466 POU domain, class 2, transcription factor 3 Human genes 0.000 description 1
- 101100139878 Schizosaccharomyces pombe (strain 972 / ATCC 24843) ran1 gene Proteins 0.000 description 1
- 101000986981 Tropidechis carinatus Acidic phospholipase A2 1 Proteins 0.000 description 1
- 238000004364 calculation method Methods 0.000 description 1
- 230000006835 compression Effects 0.000 description 1
- 238000007906 compression Methods 0.000 description 1
- 238000007796 conventional method Methods 0.000 description 1
- 230000001934 delay Effects 0.000 description 1
- 230000003111 delayed effect Effects 0.000 description 1
- 238000012938 design process Methods 0.000 description 1
- 238000011161 development Methods 0.000 description 1
- 238000006073 displacement reaction Methods 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 239000000835 fiber Substances 0.000 description 1
- 101150101567 pat-2 gene Proteins 0.000 description 1
- 238000011057 process analytical technology Methods 0.000 description 1
- 238000003672 processing method Methods 0.000 description 1
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L7/00—Arrangements for synchronising receiver with transmitter
- H04L7/04—Speed or phase control by synchronisation signals
- H04L7/041—Speed or phase control by synchronisation signals using special codes as synchronising signal
- H04L7/042—Detectors therefor, e.g. correlators, state machines
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
- H04N5/00—Details of television systems
- H04N5/04—Synchronising
Landscapes
- Engineering & Computer Science (AREA)
- Signal Processing (AREA)
- Computer Networks & Wireless Communication (AREA)
- Multimedia (AREA)
- Synchronisation In Digital Transmission Systems (AREA)
- Compression Or Coding Systems Of Tv Signals (AREA)
- Time-Division Multiplex Systems (AREA)
Abstract
(57)【要約】 （修正有）
【目的】 マルチメディア等高速の処理速度を求めるシ
ステムが、可変長さ符号の伝送誤謬に対し迅速に対処で
きるように、伝送誤謬が発生した可変長さ符号ビット列
で、同期符号を高速に探索することができるようにす
る。 【構成】 入力ビット列でn+1個の単位ビットほど入力
されるビット列をPLAに伝え、入力ビット列で同期符号
とマッチするパターンを探索するため入力ビット列に対
し同期符号パターンを１ビットずつ順次シフトさせ入力
ビット列と夫々並列比較する。パターンマッチにならな
いと、パターンマッチになるまで累算機に入力した数ほ
ど次に連結する入力ビット列を前記PLAに伝えられるよ
うにする。パターンマッチが発見されると前記ＰＬＡで
パターン発見信号を制御部に送り、累算機に入力したパ
ターンマッチになったビット数をベラルシフトに送り、
ベラルシフトで前記ビット数ほど入力ビット数がシフト
されるようにする。
ステムが、可変長さ符号の伝送誤謬に対し迅速に対処で
きるように、伝送誤謬が発生した可変長さ符号ビット列
で、同期符号を高速に探索することができるようにす
る。 【構成】 入力ビット列でn+1個の単位ビットほど入力
されるビット列をPLAに伝え、入力ビット列で同期符号
とマッチするパターンを探索するため入力ビット列に対
し同期符号パターンを１ビットずつ順次シフトさせ入力
ビット列と夫々並列比較する。パターンマッチにならな
いと、パターンマッチになるまで累算機に入力した数ほ
ど次に連結する入力ビット列を前記PLAに伝えられるよ
うにする。パターンマッチが発見されると前記ＰＬＡで
パターン発見信号を制御部に送り、累算機に入力したパ
ターンマッチになったビット数をベラルシフトに送り、
ベラルシフトで前記ビット数ほど入力ビット数がシフト
されるようにする。
Description
【０００１】
【産業上の利用分野】本発明はＢ−ＩＳＤＮ端末機、高
鮮明テレビジョン、ディジタルテレビジョン、マルチメ
ディア、ビデオテックス、ファクシミリ等に用いる可変
長さ復号化部において、受信した可変長さ符号に伝送誤
謬が発生した場合、並列処理パターンマッチングを用い
て可変長さ符号を高速に再同期させる方法に関するもの
である。
鮮明テレビジョン、ディジタルテレビジョン、マルチメ
ディア、ビデオテックス、ファクシミリ等に用いる可変
長さ復号化部において、受信した可変長さ符号に伝送誤
謬が発生した場合、並列処理パターンマッチングを用い
て可変長さ符号を高速に再同期させる方法に関するもの
である。
【０００２】
【従来の技術】現在、統計的重複性を有する全てのデー
タ等は、伝送効率を極大化するために、可変長さ符号を
用い圧縮して伝送される。前記可変長さ符号は伝送誤謬
が発生した場合伝送誤謬の遅延を誘発させる。このた
め、前記可変長さ符号には伝送誤謬が発生した場合、伝
送誤謬の電波を最少化するため固定長さの同期符号が付
加される。
タ等は、伝送効率を極大化するために、可変長さ符号を
用い圧縮して伝送される。前記可変長さ符号は伝送誤謬
が発生した場合伝送誤謬の遅延を誘発させる。このた
め、前記可変長さ符号には伝送誤謬が発生した場合、伝
送誤謬の電波を最少化するため固定長さの同期符号が付
加される。
【０００３】前記可変長さ符号は、符号化しようとする
シンボルの統計的分布により発生頻度が高いシンボルに
は少ないビットを割り当て、発生頻度が低いシンボルに
は多いビットを割り当てることにより得られる。前記可
変長さ符号を用いると、固定長さ符号 (FLC:Fixed Leng
th coding）の使用に比べ効果的にビット発生率を軽減
することができる。前記可変長さ符号は、データの統計
的重複性を取り除き伝送媒体を経て伝送されたり記録媒
体に貯蔵された多量の映像及び音声データを、大きく減
少させる。
シンボルの統計的分布により発生頻度が高いシンボルに
は少ないビットを割り当て、発生頻度が低いシンボルに
は多いビットを割り当てることにより得られる。前記可
変長さ符号を用いると、固定長さ符号 (FLC:Fixed Leng
th coding）の使用に比べ効果的にビット発生率を軽減
することができる。前記可変長さ符号は、データの統計
的重複性を取り除き伝送媒体を経て伝送されたり記録媒
体に貯蔵された多量の映像及び音声データを、大きく減
少させる。
【０００４】しかし、前記可変長さ符号は次のような欠
点を有する。第一の欠点は、前記可変長さ符号ビット列
を復号する場合、各シンボルが統計的分布により相違す
る長さを有するシンボルに復号されることである。この
ため復号機のハードウェアの複雑度が増加する。他の一
つの欠点は、伝送誤謬が発生した場合、元来伝送しよう
とする符号とは異なる長さを有する符号に復号され、復
号機でこの伝送誤謬を認識するまで引き続き次の符号に
影響を与えることである。
点を有する。第一の欠点は、前記可変長さ符号ビット列
を復号する場合、各シンボルが統計的分布により相違す
る長さを有するシンボルに復号されることである。この
ため復号機のハードウェアの複雑度が増加する。他の一
つの欠点は、伝送誤謬が発生した場合、元来伝送しよう
とする符号とは異なる長さを有する符号に復号され、復
号機でこの伝送誤謬を認識するまで引き続き次の符号に
影響を与えることである。
【０００５】可変長さ符号の符号機は、伝送誤謬により
データの処理が遅延するのを防ぐため、固定長さの同期
符号を可変長さ符号に付加する。一方、可変長さ復号機
は可変長さ符号に発生した伝送誤謬を認識した場合に、
前記同期符号を探索することにより前記可変長さ符号と
再同期することになる。また、一つのチャンネルから他
のチャンネルに移動した場合にも、前記可変長さ復号機
は前記可変長さ符号との再同期動作を必要とする。前記
可変長さ復号機が前記可変長さ符号と再同期以後に、前
記可変長さ符号等は正しく復号される。高鮮明テレビジ
ョン、Ｂ−ＩＳＤＮ端末機、及びマルチメディアのよう
に早い処理速度を求める場合には、高速再同期アルゴリ
ズムにより、復号機をもって伝送誤謬に対する迅速な対
応が可能となる。
データの処理が遅延するのを防ぐため、固定長さの同期
符号を可変長さ符号に付加する。一方、可変長さ復号機
は可変長さ符号に発生した伝送誤謬を認識した場合に、
前記同期符号を探索することにより前記可変長さ符号と
再同期することになる。また、一つのチャンネルから他
のチャンネルに移動した場合にも、前記可変長さ復号機
は前記可変長さ符号との再同期動作を必要とする。前記
可変長さ復号機が前記可変長さ符号と再同期以後に、前
記可変長さ符号等は正しく復号される。高鮮明テレビジ
ョン、Ｂ−ＩＳＤＮ端末機、及びマルチメディアのよう
に早い処理速度を求める場合には、高速再同期アルゴリ
ズムにより、復号機をもって伝送誤謬に対する迅速な対
応が可能となる。
【０００６】既存の順次パターンマッチングのアルゴリ
ズムは、処理速度が遅く実際的にＢ−ＩＳＤＮ端末機、
高鮮明テレビジョン及びマルチメディア等高速の処理速
度を求めるシステムの直接的な適用には不適切である。
前記問題点を表１と関連して説明すると、入力ビット列
Ｓ(t）は同期符号パターン (ＰＡＴ）と較べて一致しな
い場合は１ビット分シフトする。また前記シフトした入
力ビット列Ｓ (t+１）は同期符号パターン (ＰＡＴ)と
較べて一致しない場合は再度１ビットほどシフトする。
このような方法で前記入力ビット列Ｓ(t+n）は同期符号
パターン (ＰＡＴ）と一致するまで繰返し同期符号パタ
ーンと比較され、そしてシフトされる。
ズムは、処理速度が遅く実際的にＢ−ＩＳＤＮ端末機、
高鮮明テレビジョン及びマルチメディア等高速の処理速
度を求めるシステムの直接的な適用には不適切である。
前記問題点を表１と関連して説明すると、入力ビット列
Ｓ(t）は同期符号パターン (ＰＡＴ）と較べて一致しな
い場合は１ビット分シフトする。また前記シフトした入
力ビット列Ｓ (t+１）は同期符号パターン (ＰＡＴ)と
較べて一致しない場合は再度１ビットほどシフトする。
このような方法で前記入力ビット列Ｓ(t+n）は同期符号
パターン (ＰＡＴ）と一致するまで繰返し同期符号パタ
ーンと比較され、そしてシフトされる。
【０００７】
【表１】
【０００８】以下、このアルゴリズムについて具体的に
説明する。入力ビット列、即ち、文字列Ｓは‘s1,s2,s3
・・・sI-1,si,si+1,si+2,・・・sL'であり、この文字列から
見出そうとするマッチパターンＰＡＴは‘p1,p2,p3,p4,
・・・pn'とする (n≪L）。文字列Ｓのsi+1はＰＡＴのp1と
比較される。si+1からsi+3までp1からp3まで一致し、si
+4とp4が一致しないと仮定する。この時、パターンマッ
チングは失敗することになり、マッチパターンＰＡＴは
文字列Ｓのsi+2から始め再びp1と較べる。この過程を文
字列Ｓが終わるまで繰り返すとすれば、パターンマッチ
ングをするために、マッチパターンＰＡＴはL-n+1ほど
移動することになる。一度移動した場合に較べた演算の
数をＫに示すと、比較する一番目のパターン即ちp1とsi
+1が相違する場合Ｋ値は１になり、最悪の場合、即ちpn
-1までパターンが同様でありpnパターンが異なる場合Ｋ
の値はnになる。
説明する。入力ビット列、即ち、文字列Ｓは‘s1,s2,s3
・・・sI-1,si,si+1,si+2,・・・sL'であり、この文字列から
見出そうとするマッチパターンＰＡＴは‘p1,p2,p3,p4,
・・・pn'とする (n≪L）。文字列Ｓのsi+1はＰＡＴのp1と
比較される。si+1からsi+3までp1からp3まで一致し、si
+4とp4が一致しないと仮定する。この時、パターンマッ
チングは失敗することになり、マッチパターンＰＡＴは
文字列Ｓのsi+2から始め再びp1と較べる。この過程を文
字列Ｓが終わるまで繰り返すとすれば、パターンマッチ
ングをするために、マッチパターンＰＡＴはL-n+1ほど
移動することになる。一度移動した場合に較べた演算の
数をＫに示すと、比較する一番目のパターン即ちp1とsi
+1が相違する場合Ｋ値は１になり、最悪の場合、即ちpn
-1までパターンが同様でありpnパターンが異なる場合Ｋ
の値はnになる。
【０００９】前記の例でsi+3とp3まで一致したのでＫ値
は3となる。それ故にＫの値の範囲は次の通りである。1
＜Ｋ＜n、従って総演算の数は次の式により計算され
る。 この時、Ｋ値は比較する文字列の特性により左右され
る。文字列が二進数のランダム ビット列と仮定すれば
Ｋの平均値は次の式に表される。 よってＫの値はt値が大きいほど増加幅は少なくなる。
若しn値が∞と仮定すればＫ,の平均値は2になる。前記
アルゴ リズムはパターン マッチングが中途で失敗した
場合文字列Ｓをsi+2からＰＡＴのp1と再び較べなければ
ならず、ハードウェアに示す場合に文字列Ｓを含むバッ
ファを制御しなければならない欠点を有する。
は3となる。それ故にＫの値の範囲は次の通りである。1
＜Ｋ＜n、従って総演算の数は次の式により計算され
る。 この時、Ｋ値は比較する文字列の特性により左右され
る。文字列が二進数のランダム ビット列と仮定すれば
Ｋの平均値は次の式に表される。 よってＫの値はt値が大きいほど増加幅は少なくなる。
若しn値が∞と仮定すればＫ,の平均値は2になる。前記
アルゴ リズムはパターン マッチングが中途で失敗した
場合文字列Ｓをsi+2からＰＡＴのp1と再び較べなければ
ならず、ハードウェアに示す場合に文字列Ｓを含むバッ
ファを制御しなければならない欠点を有する。
【００１０】上記したアルゴリズムより求めるマッチパ
ターンＰＡＴを文字列Ｓから速く探索し、ハードウェア
で示す場合文字列Ｓを含むバッファの制御が容易であ
る。このアルゴリズムの基本概念は次の通りである。si
+1からsi+4までp1とp4が一致し、si+5とp5が一致しない
場合、ＰＡＴのp1とp4の情報を知っているとすればsi+2
とp1を再び比較せず、si+5とpk (k＜5）を較べることに
より比較演算の数を減らすことができるだけでなく、以
前に較べた文字列Ｓの中si+1、si+2、si+3、si+4を再び
較べないことによりバッファ制御が不必要となる。この
時、si+5とpkの関係を規定する関数を失敗関数F (）と
定義する。
ターンＰＡＴを文字列Ｓから速く探索し、ハードウェア
で示す場合文字列Ｓを含むバッファの制御が容易であ
る。このアルゴリズムの基本概念は次の通りである。si
+1からsi+4までp1とp4が一致し、si+5とp5が一致しない
場合、ＰＡＴのp1とp4の情報を知っているとすればsi+2
とp1を再び比較せず、si+5とpk (k＜5）を較べることに
より比較演算の数を減らすことができるだけでなく、以
前に較べた文字列Ｓの中si+1、si+2、si+3、si+4を再び
較べないことによりバッファ制御が不必要となる。この
時、si+5とpkの関係を規定する関数を失敗関数F (）と
定義する。
【００１１】定義１：ＰＡＴ＝‘p1,p2,・・・pn'に与えら
れると、このパターンに対する失敗関数F (）は次のよ
うに定義される。 F(j)＝k if p1,p2,p3 ・・・pk＝pj-k+1,pj-k+2, ・・・pj-k+n (if an k＞＝1 exists) ＝0 other wise ・・・・・・・・・・・・・・・・・・・・・・・・・・・(３)
れると、このパターンに対する失敗関数F (）は次のよ
うに定義される。 F(j)＝k if p1,p2,p3 ・・・pk＝pj-k+1,pj-k+2, ・・・pj-k+n (if an k＞＝1 exists) ＝0 other wise ・・・・・・・・・・・・・・・・・・・・・・・・・・・(３)
【００１２】例えば、上記した表１のパターンでＰＡＴ
＝‘a,b,c,a,b,c,a,c,a,b'とすれば次のような失敗関数
が得られる。 j :12345678910 ＰＡＴ :abcabcacab F(j) :0001234012
＝‘a,b,c,a,b,c,a,c,a,b'とすれば次のような失敗関数
が得られる。 j :12345678910 ＰＡＴ :abcabcacab F(j) :0001234012
【００１３】前記のような失敗関数を利用しパターン
マッチングが失敗した場合、その次の比較パターンの位
置は次の式から求められる。 次の位置 (next location) (j) ＝0 if j＝1・・・・・・・・・(４) ＝F (j-1) +1 if j≠1
マッチングが失敗した場合、その次の比較パターンの位
置は次の式から求められる。 次の位置 (next location) (j) ＝0 if j＝1・・・・・・・・・(４) ＝F (j-1) +1 if j≠1
【００１４】例えば、前記マッチパターンＰＡＴを次の
文字列S＝‘・・・a,b,c,a,c,b,c,a,c,c,a,c,a,b・・・'にパ
ターンマッチングすると、p5＝bとsi+5＝cが一致しない
ことが判る。この場合j＝5であるのでその次の比較パタ
ーンの位置は前記の式により次のように求めることがで
きる。F(5-1)+1＝2、文字列Sをsi+2からＰＡＴのp1と再
び比較せず、p2＝bとsi+5＝cを再び比較して比較演算の
回数を最少化することができる。
文字列S＝‘・・・a,b,c,a,c,b,c,a,c,c,a,c,a,b・・・'にパ
ターンマッチングすると、p5＝bとsi+5＝cが一致しない
ことが判る。この場合j＝5であるのでその次の比較パタ
ーンの位置は前記の式により次のように求めることがで
きる。F(5-1)+1＝2、文字列Sをsi+2からＰＡＴのp1と再
び比較せず、p2＝bとsi+5＝cを再び比較して比較演算の
回数を最少化することができる。
【００１５】前記のように失敗関数を用いる場合次の二
つの長所がある。一番目はパターンマッチングが失敗し
た場合文字列Ｓの中、以前に較べた文字列は再び較べな
くても良いということであり、従って文字列Ｓを含んで
いるバッファの制御が容易であるということである。二
番目は失敗関数を用いて演算の数を最少化したことであ
る。
つの長所がある。一番目はパターンマッチングが失敗し
た場合文字列Ｓの中、以前に較べた文字列は再び較べな
くても良いということであり、従って文字列Ｓを含んで
いるバッファの制御が容易であるということである。二
番目は失敗関数を用いて演算の数を最少化したことであ
る。
【００１６】
【発明が解決しようとする課題】一般的な順次パターン
マッチングのアルゴリズムと失敗関数を用いた順次パタ
ーンマッチングのアルゴリズムを説明した。しかし、こ
れらのアルゴリズムは処理速度が遅く実際にＢ−ＩＳＤ
Ｎ端末機、高鮮明テレビジョン、マルチメディア等高速
の処理速度を求めるシステムに直接適用するのは不適切
である。このようなパターンマッチングのアルゴリズム
をハードウェアに適用する場合、一つのクラックに‘si
+1・・・si+n'と‘p1・・・pn'が同時比較可能である。一般に
用いるアルゴ リズムは１．で説明した順次アルゴ リズ
ムを利用する。この方法はＰＡＴ＝‘p1,p2・・・pn'とＳ
＝‘si+1,si+2,・・・si+n'を同時に比較しＰＡＴとＳが一
致するのを一つのクラックで調査する。もし、一致しな
かった場合、マッチパターンＰＡＴを文字列Ｓに１文字
移動させた後、ＰＡＴをＳ(i+2・・・i+n+1）と比較し、も
し一致しなかった場合、再び前記の過程を繰り返す。前
記の過程の例は表１で示す通りである。この時、文字列
ＳとＰＡＴを較べるためのマッチパターンＰＡＴの総移
動回数はＬ-n+1となり、必要な演算の数は (Ｌ-n+1)×n
となる。前記のアルゴ リズムは一つのクラックに一つ
の文字だけ移動可能にする。
マッチングのアルゴリズムと失敗関数を用いた順次パタ
ーンマッチングのアルゴリズムを説明した。しかし、こ
れらのアルゴリズムは処理速度が遅く実際にＢ−ＩＳＤ
Ｎ端末機、高鮮明テレビジョン、マルチメディア等高速
の処理速度を求めるシステムに直接適用するのは不適切
である。このようなパターンマッチングのアルゴリズム
をハードウェアに適用する場合、一つのクラックに‘si
+1・・・si+n'と‘p1・・・pn'が同時比較可能である。一般に
用いるアルゴ リズムは１．で説明した順次アルゴ リズ
ムを利用する。この方法はＰＡＴ＝‘p1,p2・・・pn'とＳ
＝‘si+1,si+2,・・・si+n'を同時に比較しＰＡＴとＳが一
致するのを一つのクラックで調査する。もし、一致しな
かった場合、マッチパターンＰＡＴを文字列Ｓに１文字
移動させた後、ＰＡＴをＳ(i+2・・・i+n+1）と比較し、も
し一致しなかった場合、再び前記の過程を繰り返す。前
記の過程の例は表１で示す通りである。この時、文字列
ＳとＰＡＴを較べるためのマッチパターンＰＡＴの総移
動回数はＬ-n+1となり、必要な演算の数は (Ｌ-n+1)×n
となる。前記のアルゴ リズムは一つのクラックに一つ
の文字だけ移動可能にする。
【００１７】前記したように従来の技術は可変長さ符号
の伝送誤謬が発生した場合、可変長さ符号に固定長さを
有する同期符号の探索に時間が非常に多く要するので、
高速の処理を求めるシステムに適用するには限界があ
る。よって、本発明の目的はB-ISDN端末機、高鮮明テレ
ビジョン、マルチメディア等高速の処理速度を求めるシ
ステムが受信される可変長さ符号の伝送誤謬に迅速に対
応することができるよう、伝送誤謬が発生した可変長さ
符号ビット列で求める同期符号を高速に探索することが
できる並列処理パターン マッチングを用いた可変長さ
符号の高速再同期方法を提供することにある。
の伝送誤謬が発生した場合、可変長さ符号に固定長さを
有する同期符号の探索に時間が非常に多く要するので、
高速の処理を求めるシステムに適用するには限界があ
る。よって、本発明の目的はB-ISDN端末機、高鮮明テレ
ビジョン、マルチメディア等高速の処理速度を求めるシ
ステムが受信される可変長さ符号の伝送誤謬に迅速に対
応することができるよう、伝送誤謬が発生した可変長さ
符号ビット列で求める同期符号を高速に探索することが
できる並列処理パターン マッチングを用いた可変長さ
符号の高速再同期方法を提供することにある。
【００１８】
【課題を解決するための手段】本発明は高鮮明テレビジ
ョン、ディジタル テレビジョン、マルチメディアシス
テム等の可変長さ符号で伝送誤謬が発生した場合、伝送
したビット列を復旧するため同期符号を探索する方法に
おいて、辺長さ移動量をもって入力される入力ビット列
で高速に同期符号を探索するため、ビット列でn+1個の
単位ビットほど入力されるビット列をＰＡＬ (Program
Logic Array）に伝え、入力ビット列で同期符号とマッ
チするパターンを探索するため入力ビット列に対し同期
符号パターンを１ビットずつ順次シフトさせ、入力ビッ
ト列と夫々並列比較しパターンマッチになるか否かを比
較し、パターンマッチが発見されなければパターンマッ
チになるまで累算機に入力された数ほど次に連結する入
力ビット列を前記ＰＬＡへ伝えるようにし、パターンマ
ッチが発見されると前記PALでパターン発見信号を制御
部に送り、累算機に入力された前記パターンマッチとな
ったビット数をベラルシフトに送り、ベラルシフトで前
記ビット数ほど入力ビット数がシフトされるようにして
同期符号を入力ビット列より正確に探索する並列処理パ
ターンマッチングを用いた可変長さ符号の高速再同期方
法を提供するものである。
ョン、ディジタル テレビジョン、マルチメディアシス
テム等の可変長さ符号で伝送誤謬が発生した場合、伝送
したビット列を復旧するため同期符号を探索する方法に
おいて、辺長さ移動量をもって入力される入力ビット列
で高速に同期符号を探索するため、ビット列でn+1個の
単位ビットほど入力されるビット列をＰＡＬ (Program
Logic Array）に伝え、入力ビット列で同期符号とマッ
チするパターンを探索するため入力ビット列に対し同期
符号パターンを１ビットずつ順次シフトさせ、入力ビッ
ト列と夫々並列比較しパターンマッチになるか否かを比
較し、パターンマッチが発見されなければパターンマッ
チになるまで累算機に入力された数ほど次に連結する入
力ビット列を前記ＰＬＡへ伝えるようにし、パターンマ
ッチが発見されると前記PALでパターン発見信号を制御
部に送り、累算機に入力された前記パターンマッチとな
ったビット数をベラルシフトに送り、ベラルシフトで前
記ビット数ほど入力ビット数がシフトされるようにして
同期符号を入力ビット列より正確に探索する並列処理パ
ターンマッチングを用いた可変長さ符号の高速再同期方
法を提供するものである。
【００１９】
【実施例】本発明は、同時に処理する比較演算の数を増
加させ、一つのクラックに一つ以上の移動量を有する二
つのアルゴリズムを提案するものである第一に、可変長
さ移動量を有するパターン マッチングを検討してみ
る。マッチパターンＰＡＴとＳ (i+1・・・i+n）のパター
ン マッチングが失敗し、文字列の最終si+n-k+1からsi+
nまでp1でpkと一致したと仮定する (k＜n）。この時、
‘p1,p2・・・pk'＝‘si+n-k+1・・・si+n-1,si+n'なので、次
の状態ではマッチパターンＰＡＴを文字列Ｓでn-kほど
移動し再びマッチパターンＰＡＴと文字列Ｓを較べる。
この方法は以前に較べた文字列Ｓの中‘si+1,si+2・・・si
+n-k'を再び較べなくても良いので高速処理が可能であ
る。この文字列Ｓ (si+n-k+1・・・si+n）とＰＡＴ (p1・・・
pk）と一致するkの最大値と、次の状態でのマッチパタ
ーンＰＡＴの移動量及び比較するＰＡＴの位置は一般に
次のように求めることができる。
加させ、一つのクラックに一つ以上の移動量を有する二
つのアルゴリズムを提案するものである第一に、可変長
さ移動量を有するパターン マッチングを検討してみ
る。マッチパターンＰＡＴとＳ (i+1・・・i+n）のパター
ン マッチングが失敗し、文字列の最終si+n-k+1からsi+
nまでp1でpkと一致したと仮定する (k＜n）。この時、
‘p1,p2・・・pk'＝‘si+n-k+1・・・si+n-1,si+n'なので、次
の状態ではマッチパターンＰＡＴを文字列Ｓでn-kほど
移動し再びマッチパターンＰＡＴと文字列Ｓを較べる。
この方法は以前に較べた文字列Ｓの中‘si+1,si+2・・・si
+n-k'を再び較べなくても良いので高速処理が可能であ
る。この文字列Ｓ (si+n-k+1・・・si+n）とＰＡＴ (p1・・・
pk）と一致するkの最大値と、次の状態でのマッチパタ
ーンＰＡＴの移動量及び比較するＰＡＴの位置は一般に
次のように求めることができる。
【００２０】もし、‘p1,p2,p3・・・pk'＝‘si+n-k+1,si+
n-k+2,・・・si+n' (0＜＝k＜＝n）であり‘pk+1'≠‘si+n
-k'の際、次の状態でマッチパターンＰＡＴの移動量はn
-kとなり、次の状態で較べるＰＡＴの位置＝k+1とな
る。例えば例示のパターンでＰＡＴ＝‘p1,p2,p3,p4・・・
pn'＝‘a,b,c,a,b,c,a,c,a,b',n＝10,とし、文字列Ｓ＝
‘si+1,si+2,・・・,si+n,si+n+1,si+n+2・・・'＝‘・・・・c,d,
a,f,g,c,a,b,c,a,b,c,a,c,・・・'とすれば、マッチパター
ンＰＡＴの移動量とその次の比較パターンの位置は表２
のように求めることができる。この例で‘p1,p2,p3,p4'
＝‘si+n-3,si+n-2,si+n-1,si+n'なのでk＝4になり、マ
ッチパターンの文字列Ｓでの移動量はn-kにより6にな
る。ＰＡＴが6ほど移動した後次の状態に移ることにな
る。ＰＡＴ＝‘p5,p6,p7,p8,p9,p10'と‘si+5,si+6,si+
7,si+8,si+9,si+10'と較べる。若し文字列Ｓがランダム
したパターン特性を有すればkの値は殆ど0に近くなる。
この時、文字列ＳとＰＡＴを較べるための総移動回数は
L/nとなり、必要な演算の数は(L/n)×n＝Lになる。よっ
て、一般的なパターンマッチングをハードウェアに適用
した場合と比較して処理速度が非常に高速である。
n-k+2,・・・si+n' (0＜＝k＜＝n）であり‘pk+1'≠‘si+n
-k'の際、次の状態でマッチパターンＰＡＴの移動量はn
-kとなり、次の状態で較べるＰＡＴの位置＝k+1とな
る。例えば例示のパターンでＰＡＴ＝‘p1,p2,p3,p4・・・
pn'＝‘a,b,c,a,b,c,a,c,a,b',n＝10,とし、文字列Ｓ＝
‘si+1,si+2,・・・,si+n,si+n+1,si+n+2・・・'＝‘・・・・c,d,
a,f,g,c,a,b,c,a,b,c,a,c,・・・'とすれば、マッチパター
ンＰＡＴの移動量とその次の比較パターンの位置は表２
のように求めることができる。この例で‘p1,p2,p3,p4'
＝‘si+n-3,si+n-2,si+n-1,si+n'なのでk＝4になり、マ
ッチパターンの文字列Ｓでの移動量はn-kにより6にな
る。ＰＡＴが6ほど移動した後次の状態に移ることにな
る。ＰＡＴ＝‘p5,p6,p7,p8,p9,p10'と‘si+5,si+6,si+
7,si+8,si+9,si+10'と較べる。若し文字列Ｓがランダム
したパターン特性を有すればkの値は殆ど0に近くなる。
この時、文字列ＳとＰＡＴを較べるための総移動回数は
L/nとなり、必要な演算の数は(L/n)×n＝Lになる。よっ
て、一般的なパターンマッチングをハードウェアに適用
した場合と比較して処理速度が非常に高速である。
【００２１】
【表２】
【００２２】第二に、固定長さ移動量を有するパターン
マッチングに対し検討してみることにする。文字列Ｓの
中、マッチパターンＰＡＴと較べる現在の状態をＳ(t)
に表示し、比較後文字列Ｓをnほど移動させてマッチパ
ターンＰＡＴと較べる次の状態をＳ(t+1)に表示する。
マッチパターンＰＡＴ(1・・・n)とＳ(t,1・・・n)のパターン
マッチングが失敗し、文字列の最終sn-k+1からsnまでp1
でpkと一致されたと仮定する (k＜n）。この時‘p1,p2・
・・pk'＝‘sn-k+1・・・sn-1,sn'となる。このkの値を順方
向マッチ数という。次の状態でマッチパターンＰＡＴ(p
k+1・・・pn)をＳ(t+1,1・・・n)と較べる。この時‘pk+1,p+
2,・・・pn'と‘s1,s2,・・・sn-k'が同じ場合求めるパターン
を発見することになる。この過程を表３を参照しながら
説明する。マッチパターンを‘a,b,c,a,b,c,a,c,f,b',n
＝10,とし、比較文字列Ｓを‘b,b,c,a,a,c,a,d,a,b,f,
b,a,d,g,c,a,b,c,a, b,c,a,c,f,b,a,d,c,a, a,b,c,a,b,
c,a,c,f,b'とする。この時、Ｓをマッチ パターンＰＡ
Ｔと10文字ずつ較べて見る場合、s(t)＝‘b,b,c,a,a,c,
a,d,a,b', Ｓ(t+1)＝‘f,b,a,d,g,c,a,b,c,a', Ｓ(t+2)
＝‘b,c,a,c,f,b,a,d,c,a', Ｓ(t+3)＝‘a,b,c,a,b,c,
a,c,f,b'となり夫々マッチ パターンＰＡＴと較べるこ
とになる。一番目の文字列s(t)とパターン文字ＰＡＴの
初めから順方向に較べる場合‘・・・a,b'＝‘a,b・・・',即
ち順方向マッチ数k＝2となる。次にＳ(t+1)とパターン
文字ＰＡＴの最後から逆方向に較べる場合‘f,b,・・・'と
‘・・・f,b'が較べられるので逆方向マッチ数は2となる。
そのため順方向マッチ数と2との和が10にならないので
パターン マッチングされない。Ｓ(t+1)とＰＡＴが順方
向で較べる場合‘・・・a,b,c,a'＝‘a,b,c,a・・・',即ち順
方向マッチ数、k＝4となる。Ｓ(t+2)とＰＡＴを再び逆
方向に較べると‘b,c,a,c,f,b・・・'及び‘・・・b,c,a,c,f,
b'が比較されるため、ＰＡＴの6個の後の文字列と比較
される。その結果、逆方向マッチ数は6となる。この値
と順方向マッチ数4との和が10となる。よって求める文
字列がＳ(t+1)とＳ(t+2)にあることが判る。Ｓ(t+2)と
パターン文字ＰＡＴを順方向に較べる場合‘・・・a'＝‘a
・・・',即ち順方向マッチ数k＝1となる。Ｓ(t+3)とＰＡＴ
を較べると文字が全部一致するのでk＝10になり以前の
順方向マッチ数と係りなくパターン マッチが行われる
ようになる。この文字列ＳとＰＡＴを較べるための総移
動回数はL/nとなり、必要な演算の数は(L/n)×n＝Lとな
る。
マッチングに対し検討してみることにする。文字列Ｓの
中、マッチパターンＰＡＴと較べる現在の状態をＳ(t)
に表示し、比較後文字列Ｓをnほど移動させてマッチパ
ターンＰＡＴと較べる次の状態をＳ(t+1)に表示する。
マッチパターンＰＡＴ(1・・・n)とＳ(t,1・・・n)のパターン
マッチングが失敗し、文字列の最終sn-k+1からsnまでp1
でpkと一致されたと仮定する (k＜n）。この時‘p1,p2・
・・pk'＝‘sn-k+1・・・sn-1,sn'となる。このkの値を順方
向マッチ数という。次の状態でマッチパターンＰＡＴ(p
k+1・・・pn)をＳ(t+1,1・・・n)と較べる。この時‘pk+1,p+
2,・・・pn'と‘s1,s2,・・・sn-k'が同じ場合求めるパターン
を発見することになる。この過程を表３を参照しながら
説明する。マッチパターンを‘a,b,c,a,b,c,a,c,f,b',n
＝10,とし、比較文字列Ｓを‘b,b,c,a,a,c,a,d,a,b,f,
b,a,d,g,c,a,b,c,a, b,c,a,c,f,b,a,d,c,a, a,b,c,a,b,
c,a,c,f,b'とする。この時、Ｓをマッチ パターンＰＡ
Ｔと10文字ずつ較べて見る場合、s(t)＝‘b,b,c,a,a,c,
a,d,a,b', Ｓ(t+1)＝‘f,b,a,d,g,c,a,b,c,a', Ｓ(t+2)
＝‘b,c,a,c,f,b,a,d,c,a', Ｓ(t+3)＝‘a,b,c,a,b,c,
a,c,f,b'となり夫々マッチ パターンＰＡＴと較べるこ
とになる。一番目の文字列s(t)とパターン文字ＰＡＴの
初めから順方向に較べる場合‘・・・a,b'＝‘a,b・・・',即
ち順方向マッチ数k＝2となる。次にＳ(t+1)とパターン
文字ＰＡＴの最後から逆方向に較べる場合‘f,b,・・・'と
‘・・・f,b'が較べられるので逆方向マッチ数は2となる。
そのため順方向マッチ数と2との和が10にならないので
パターン マッチングされない。Ｓ(t+1)とＰＡＴが順方
向で較べる場合‘・・・a,b,c,a'＝‘a,b,c,a・・・',即ち順
方向マッチ数、k＝4となる。Ｓ(t+2)とＰＡＴを再び逆
方向に較べると‘b,c,a,c,f,b・・・'及び‘・・・b,c,a,c,f,
b'が比較されるため、ＰＡＴの6個の後の文字列と比較
される。その結果、逆方向マッチ数は6となる。この値
と順方向マッチ数4との和が10となる。よって求める文
字列がＳ(t+1)とＳ(t+2)にあることが判る。Ｓ(t+2)と
パターン文字ＰＡＴを順方向に較べる場合‘・・・a'＝‘a
・・・',即ち順方向マッチ数k＝1となる。Ｓ(t+3)とＰＡＴ
を較べると文字が全部一致するのでk＝10になり以前の
順方向マッチ数と係りなくパターン マッチが行われる
ようになる。この文字列ＳとＰＡＴを較べるための総移
動回数はL/nとなり、必要な演算の数は(L/n)×n＝Lとな
る。
【００２３】
【表３】
【００２４】並列処理パターン マッチングに対し検討
してみることにする。マッチパターンは長さがn bitの
ＰＡＴであり、このマッチパターンと較べるためハード
ウェアに与えられた入力ビット列の長さをdビットであ
るs(t)とする(n＜d）。並列処理パターンマッチのアル
ゴリズムには次の二つの種類を考慮してみることができ
る。
してみることにする。マッチパターンは長さがn bitの
ＰＡＴであり、このマッチパターンと較べるためハード
ウェアに与えられた入力ビット列の長さをdビットであ
るs(t)とする(n＜d）。並列処理パターンマッチのアル
ゴリズムには次の二つの種類を考慮してみることができ
る。
【００２５】第１は、ＰＡＴの並列処理はＰＡＴ＝pat1
+pat2+・・・pati+・・・patk (patiの長さ＝p）の場合patiを
夫々Ｓ(t)で独立的に探索する場合を意味する。kが１の
場合には与えられたＳ(t)に対し最大移動量になるため
必要な最小の比較量は並列マッチングされなかった場合
と同一である。
+pat2+・・・pati+・・・patk (patiの長さ＝p）の場合patiを
夫々Ｓ(t)で独立的に探索する場合を意味する。kが１の
場合には与えられたＳ(t)に対し最大移動量になるため
必要な最小の比較量は並列マッチングされなかった場合
と同一である。
【００２６】第２は、Ｓ(t)の並列処理はＳ(t)の長さが
dであり、d＝d1+d2・・・dj (d1＝d2＝・・・dj＝n）で構成さ
れていた場合、夫々のdjビットでpattを並列マッチング
して探索するアルゴ リズムである。この場合は前記で
説明した周期がp＝nのpattを長さがn＝dである入力ビッ
ト列で並列に探索する場合と一致する。そのため、総移
動量dを有するため必要な演算数Cは次の通りである。 Ｃ＝1/2×n×(n+1)×d/n+(1/2)×(n-1)×(n-1)×(d/n-
1)
dであり、d＝d1+d2・・・dj (d1＝d2＝・・・dj＝n）で構成さ
れていた場合、夫々のdjビットでpattを並列マッチング
して探索するアルゴ リズムである。この場合は前記で
説明した周期がp＝nのpattを長さがn＝dである入力ビッ
ト列で並列に探索する場合と一致する。そのため、総移
動量dを有するため必要な演算数Cは次の通りである。 Ｃ＝1/2×n×(n+1)×d/n+(1/2)×(n-1)×(n-1)×(d/n-
1)
【００２７】前記で展開した並列処理パターンマッチン
グのための最少比較演算回数から、並列処理パターン
マッチングのための最適のハードウェアを検討してみ
る。第１に、一つの状態でＰＡＴの移動量を最大化しな
ければならない。このためにはマッチパターンＰＡＴと
較べるＳ(t)の長さを最大化することが必要である。し
かし、Ｓ(t)の連続的な増加は一つの状態でＰＡＴの移
動量を最大化することができるが、一つの状態を行うた
めの時間遅延を誘発させる。
グのための最少比較演算回数から、並列処理パターン
マッチングのための最適のハードウェアを検討してみ
る。第１に、一つの状態でＰＡＴの移動量を最大化しな
ければならない。このためにはマッチパターンＰＡＴと
較べるＳ(t)の長さを最大化することが必要である。し
かし、Ｓ(t)の連続的な増加は一つの状態でＰＡＴの移
動量を最大化することができるが、一つの状態を行うた
めの時間遅延を誘発させる。
【００２８】第２に、一つの状態の時間をできるだけ最
少化することが必要である。これはゲートによる信号の
遅延を最少化しクリティカルパス (critical path）を
減らすことを意味する。一つの状態で時間的な遅延は通
過するゲート数により左右される。入力ビット列Ｓ(t)
でマッチ パターンの信号を求め、このパターンから移
動量を求める。移動量を求める過程では最少移動量に優
先順位を置く。優先順位が高いものから処理した後、優
先順位が低いものを判定しなければならないのでＳ(t)
の長さd値が大きいほどゲートの遅延を誘発させる。こ
のようなゲートの遅延を最少化するためdの長さをでき
るだけ短くすべきである。一つの状態を行うのに必要な
時間を最少化するためには、マッチパターンＰＡＴと較
べるＳ(t)の長さを同一にすべきである。
少化することが必要である。これはゲートによる信号の
遅延を最少化しクリティカルパス (critical path）を
減らすことを意味する。一つの状態で時間的な遅延は通
過するゲート数により左右される。入力ビット列Ｓ(t)
でマッチ パターンの信号を求め、このパターンから移
動量を求める。移動量を求める過程では最少移動量に優
先順位を置く。優先順位が高いものから処理した後、優
先順位が低いものを判定しなければならないのでＳ(t)
の長さd値が大きいほどゲートの遅延を誘発させる。こ
のようなゲートの遅延を最少化するためdの長さをでき
るだけ短くすべきである。一つの状態を行うのに必要な
時間を最少化するためには、マッチパターンＰＡＴと較
べるＳ(t)の長さを同一にすべきである。
【００２９】最後に、ロジックの複雑度を最少化しなけ
ればならない。これをＰＡＴをＳ(t)と較べるため最少
比較演算回数Cはnとなることが判る。即ち、二進数では
ＰＡＴのビット列の構成が全て１や０の場合である。一
般に高鮮明テレビジョンで用いる同期化符号のＰＡＴは
０ビットの連続でなる。
ればならない。これをＰＡＴをＳ(t)と較べるため最少
比較演算回数Cはnとなることが判る。即ち、二進数では
ＰＡＴのビット列の構成が全て１や０の場合である。一
般に高鮮明テレビジョンで用いる同期化符号のＰＡＴは
０ビットの連続でなる。
【００３０】前記の三つの条件を全て満足するためには
マッチパターンＰＡＴを同じ符号で構成し、構成したＰ
ＡＴを較べるＳ(t)の長さを最大化し、ゲートの遅延を
最小化するためＰＡＴと較べるＳ(t)の長さを最小化し
なければならない。そのため、Ｓ(t)をＳ(t)＝s1+s2・・・
+si・・・sk (length(si)＝n）で構成した後siとＰＡＴを
並列処理を介して較べることによりこの三つの条件を全
て満足することができる。このように回路を構成すると
比較演算数は0(n)、回路の複雑度は0(n) critical patt
h 0(l)に増加する反面、ＰＡＴの最大移動量は0(n)増加
する。そのためHDテレビジョンのように同期化符号を探
索するシステムで、一つの状態の時間を最少に維持しな
がら回路の複雑度を0(n)の関数に増加させることにより
パターンを探索する速度を0(n)と高速にすることができ
る。例えばＰＡＴの長さが10でありＳ(t)の長さが50で
ある場合、Ｓ(t)を10に5等分しＰＡＴの夫々並列演算で
較べることが最適である。ＰＡＴのパターンを任意に決
めることができれば、ビット列の構成を全て１や０にす
ることが回路の複雑度を最少化させ得る。
マッチパターンＰＡＴを同じ符号で構成し、構成したＰ
ＡＴを較べるＳ(t)の長さを最大化し、ゲートの遅延を
最小化するためＰＡＴと較べるＳ(t)の長さを最小化し
なければならない。そのため、Ｓ(t)をＳ(t)＝s1+s2・・・
+si・・・sk (length(si)＝n）で構成した後siとＰＡＴを
並列処理を介して較べることによりこの三つの条件を全
て満足することができる。このように回路を構成すると
比較演算数は0(n)、回路の複雑度は0(n) critical patt
h 0(l)に増加する反面、ＰＡＴの最大移動量は0(n)増加
する。そのためHDテレビジョンのように同期化符号を探
索するシステムで、一つの状態の時間を最少に維持しな
がら回路の複雑度を0(n)の関数に増加させることにより
パターンを探索する速度を0(n)と高速にすることができ
る。例えばＰＡＴの長さが10でありＳ(t)の長さが50で
ある場合、Ｓ(t)を10に5等分しＰＡＴの夫々並列演算で
較べることが最適である。ＰＡＴのパターンを任意に決
めることができれば、ビット列の構成を全て１や０にす
ることが回路の複雑度を最少化させ得る。
【００３１】本発明の第１実施例に係る、伝送誤謬が発
生した可変長さ符号ビット列で同期符号を探索するため
可変長さ移動量を有するハードウェア構造を図１に示
す。入力ビット列は入力バッファ (１０）とラッチ (１
１）を介しベラル シフト (１２）に連結され、ベラル
シフト (１２）でＰＬＡ (１３）に連結し前記ＰＬＡ
(１３）で累算機 (１４）を介し入力バッファ (１０）
とベラル シフト (１２）に連結される。可変長さ移動
量を有するためベラルシフト (１２）を用いる。ラッチ
(１１）は入力ビット列を貯蔵し、ベラルシフト (１
２）は現在入力ビット列の移動したビット列を出力させ
る。ＰＬＡ (１３）は現在入力ビット列の次の状態での
移動量を計算する。さらに求める文字列とパターン マ
ッチングか否かを示すマッチング信号を出力させる。累
算機 (１４） (accumulator）はパターン マッチングが
失敗した場合次の状態での入力ビット列の移動量を貯蔵
させ、ベラル シフト (１２）の移動量より大きい場合
は入力バッファ (１０）に信号を送り次の状態の入力ビ
ット列が入力されるようにする。
生した可変長さ符号ビット列で同期符号を探索するため
可変長さ移動量を有するハードウェア構造を図１に示
す。入力ビット列は入力バッファ (１０）とラッチ (１
１）を介しベラル シフト (１２）に連結され、ベラル
シフト (１２）でＰＬＡ (１３）に連結し前記ＰＬＡ
(１３）で累算機 (１４）を介し入力バッファ (１０）
とベラル シフト (１２）に連結される。可変長さ移動
量を有するためベラルシフト (１２）を用いる。ラッチ
(１１）は入力ビット列を貯蔵し、ベラルシフト (１
２）は現在入力ビット列の移動したビット列を出力させ
る。ＰＬＡ (１３）は現在入力ビット列の次の状態での
移動量を計算する。さらに求める文字列とパターン マ
ッチングか否かを示すマッチング信号を出力させる。累
算機 (１４） (accumulator）はパターン マッチングが
失敗した場合次の状態での入力ビット列の移動量を貯蔵
させ、ベラル シフト (１２）の移動量より大きい場合
は入力バッファ (１０）に信号を送り次の状態の入力ビ
ット列が入力されるようにする。
【００３２】即ち、0-N個のビット列を有する現在の入
力ビット列をベラルシフトを介してPAL (Program Logic
Array）に伝達し、伝達された入力ビット列と入力ビッ
ト列に対し１ビットずつ移動した多数の同期符号マッチ
パターンと、PALで並列比較し前記入力ビット列とマッ
チパターンが一致するか否かを判断し、前記入力ビット
列と前記マッチパターンが一致しないと次の入力ビット
列が前記ＰＬＡに入力されるようにして前記のように比
較作業を一致するまで実施し、入力ビット列と同期符号
パターンが一致すれば一致するビット列の数ほどベラル
シフトで現在の入力ビット列と次の入力ビット列をシフ
トさせ、シフトされた入力ビット列を前記ＰＬＡで出力
させて正確な同期信号を探索させることである。
力ビット列をベラルシフトを介してPAL (Program Logic
Array）に伝達し、伝達された入力ビット列と入力ビッ
ト列に対し１ビットずつ移動した多数の同期符号マッチ
パターンと、PALで並列比較し前記入力ビット列とマッ
チパターンが一致するか否かを判断し、前記入力ビット
列と前記マッチパターンが一致しないと次の入力ビット
列が前記ＰＬＡに入力されるようにして前記のように比
較作業を一致するまで実施し、入力ビット列と同期符号
パターンが一致すれば一致するビット列の数ほどベラル
シフトで現在の入力ビット列と次の入力ビット列をシフ
トさせ、シフトされた入力ビット列を前記ＰＬＡで出力
させて正確な同期信号を探索させることである。
【００３３】高速再同期のハードウェアに適用するアル
ゴリズムを、より容易に理解するためマッチパターン過
程を表４を参照して説明する。マッチ パターンは長さ
が５の‘00111'であり、このマッチパターンと較べるた
め入力ビット列の長さが10bitである場合、マッチパタ
ーンを入力ビット列に１bitずつ移動させたロジックと
並列処理を介し同時に入力ビット列と較べる。入力ビッ
ト列とパターン マッチングする最少のmkを求める。こ
の場合k値がベラル シフトの入力値に用いられ次の状態
で入力ビット列はkほど移動し再びマッチ パターン‘00
111'と較べられる。ここで次の状態の入力ビット列の最
大ビット移動量はマッチ パターンの長さ５により左右
されるものではなく、比較する入力ビット列の数とベラ
ル シフトの最大移動可能なビットにより左右される。
前記の例で入力ビット列が10であり10以上移動可能なベ
ラル シフトがあると仮定した場合、マッチ パターンの
最大移動量は10になる。
ゴリズムを、より容易に理解するためマッチパターン過
程を表４を参照して説明する。マッチ パターンは長さ
が５の‘00111'であり、このマッチパターンと較べるた
め入力ビット列の長さが10bitである場合、マッチパタ
ーンを入力ビット列に１bitずつ移動させたロジックと
並列処理を介し同時に入力ビット列と較べる。入力ビッ
ト列とパターン マッチングする最少のmkを求める。こ
の場合k値がベラル シフトの入力値に用いられ次の状態
で入力ビット列はkほど移動し再びマッチ パターン‘00
111'と較べられる。ここで次の状態の入力ビット列の最
大ビット移動量はマッチ パターンの長さ５により左右
されるものではなく、比較する入力ビット列の数とベラ
ル シフトの最大移動可能なビットにより左右される。
前記の例で入力ビット列が10であり10以上移動可能なベ
ラル シフトがあると仮定した場合、マッチ パターンの
最大移動量は10になる。
【００３４】
【表４】
【００３５】前記のアルゴリズムはマッチパターンを文
字列Ｓに対し求める長さ、即ち０でnの値ほど自在に移
動可能であることを前提とする。しかし、実質的にハー
ドウェアを示す場合マッチパターンの移動量を自在に調
整するためベラルシフトが必要であり、ハードウェアが
複雑になる欠点がある。
字列Ｓに対し求める長さ、即ち０でnの値ほど自在に移
動可能であることを前提とする。しかし、実質的にハー
ドウェアを示す場合マッチパターンの移動量を自在に調
整するためベラルシフトが必要であり、ハードウェアが
複雑になる欠点がある。
【００３６】よって、次に、文字列Ｓでマッチパターン
(ＰＡＴ）を探索する場合ＰＡＴの移動量をnで固定さ
せる方法を説明することにする。本発明の第２実施例に
より、伝送誤謬が発生した可変長さ符号ビット列で同期
符号を探索するため固定長さ移動量を有するハードウェ
ア構造を図２に示す。固定長さ移動量を有するためラッ
チ (２０,２１）とレジスター (２４）を用いる。ラッ
チ (２０）は０−Ｎ個のビットを有する現在の入力ビッ
ト列を貯蔵してあり、貯蔵した現在の入力ビット列と入
力ビット列に対し１ビットずつ後続ビットに移動させた
多数の同期符号マッチ パターンと、ＰＬＡ (２３）で
並列比較し一致するか否かを確認し一致するマッチ数
(順方向マッチ数）と貯蔵した現在の入力ビット列と、
入力ビット列に対し１ビットずつ前方のビットに移動さ
せた多数の同期符号マッチパターンと、ＰＬＡ (２３）
で並列比較し一致するか否かを確認して一致するマッチ
数 (逆方向マッチ数）をレジスター (２４）に貯蔵す
る。さらに、次の状態の入力ビット列をラッチ (２０）
に入力し、この時、前記現在状態の入力ビット列はラッ
チ (２１）に移動する。次の状態の入力ビット列を前記
のような方法でＰＬＡで順方向マッチ数と逆方向マッチ
数を確認し、前記現在状態の順方向マッチ数と次の状態
の逆方向マッチ数を合せて入力ビット列のN個のビット
数と同一であれば、ファインドパターン (find patter
n）という信号を制御部 (２５）に伝えシフトされるべ
き数をベラルシフト (２６）に伝え、ベラルシフト (２
６）にラッチ (t-1) (２１）とＰＬＡ (２０）で入力さ
れた現在状態の入力ビット列と、次の状態の入力ビット
列でシフトさせて入力ビット列を同期符号マッチパター
ンと一致させる。
(ＰＡＴ）を探索する場合ＰＡＴの移動量をnで固定さ
せる方法を説明することにする。本発明の第２実施例に
より、伝送誤謬が発生した可変長さ符号ビット列で同期
符号を探索するため固定長さ移動量を有するハードウェ
ア構造を図２に示す。固定長さ移動量を有するためラッ
チ (２０,２１）とレジスター (２４）を用いる。ラッ
チ (２０）は０−Ｎ個のビットを有する現在の入力ビッ
ト列を貯蔵してあり、貯蔵した現在の入力ビット列と入
力ビット列に対し１ビットずつ後続ビットに移動させた
多数の同期符号マッチ パターンと、ＰＬＡ (２３）で
並列比較し一致するか否かを確認し一致するマッチ数
(順方向マッチ数）と貯蔵した現在の入力ビット列と、
入力ビット列に対し１ビットずつ前方のビットに移動さ
せた多数の同期符号マッチパターンと、ＰＬＡ (２３）
で並列比較し一致するか否かを確認して一致するマッチ
数 (逆方向マッチ数）をレジスター (２４）に貯蔵す
る。さらに、次の状態の入力ビット列をラッチ (２０）
に入力し、この時、前記現在状態の入力ビット列はラッ
チ (２１）に移動する。次の状態の入力ビット列を前記
のような方法でＰＬＡで順方向マッチ数と逆方向マッチ
数を確認し、前記現在状態の順方向マッチ数と次の状態
の逆方向マッチ数を合せて入力ビット列のN個のビット
数と同一であれば、ファインドパターン (find patter
n）という信号を制御部 (２５）に伝えシフトされるべ
き数をベラルシフト (２６）に伝え、ベラルシフト (２
６）にラッチ (t-1) (２１）とＰＬＡ (２０）で入力さ
れた現在状態の入力ビット列と、次の状態の入力ビット
列でシフトさせて入力ビット列を同期符号マッチパター
ンと一致させる。
【００３７】該アルゴリズムをより容易に理解するた
め、マッチパターン過程を表５にレジストを用いたハー
ドウェアの設計過程を見せている。マッチパターンは長
さが５の‘00111'であり、このマッチパターンと較べる
ための入力ビット列の長さが10ビットに固定する場合、
現在入力ビット列と以前入力ビット列の順方向パターン
マッチ数から求めるパターンが存在するか否かを調べ
る。順方向マッチ数は入力ビット列の固定長さにより左
右され、逆方向マッチ数はマッチパターンの長さにより
左右される。
め、マッチパターン過程を表５にレジストを用いたハー
ドウェアの設計過程を見せている。マッチパターンは長
さが５の‘00111'であり、このマッチパターンと較べる
ための入力ビット列の長さが10ビットに固定する場合、
現在入力ビット列と以前入力ビット列の順方向パターン
マッチ数から求めるパターンが存在するか否かを調べ
る。順方向マッチ数は入力ビット列の固定長さにより左
右され、逆方向マッチ数はマッチパターンの長さにより
左右される。
【００３８】
【表５】
【００３９】本発明の第３実施例は、伝送誤謬が発生し
た可変長さ符号ビット列で同期符号を探索するため固定
長さ移動量を有する並列処理ハードウェア構造である。
固定長さ移動量を有するハードウェア構造で説明したよ
うに、入力ビット列から求めるＰＡＴを高速に探索する
ため、ＰＡＴと較べるＳ(t)の長さを最大にし、ゲート
の遅延を最少化するためＰＡＴと較べるＳ(t)の長さを
最少化しなければならない。そのため、Ｓ(t)をＳ(t)＝
s1+s2・・・+si・・・+sk(length(si)＝n）に構成した後siと
ＰＡＴを並列処理を介して較べることにより前記条件を
全て満足することができる。もし、Ｓ(t)の長さがdであ
りＰＡＴの長さがnとした場合、d＝3nである場合の並列
処理パターンマッチングの構造を図３に示す。
た可変長さ符号ビット列で同期符号を探索するため固定
長さ移動量を有する並列処理ハードウェア構造である。
固定長さ移動量を有するハードウェア構造で説明したよ
うに、入力ビット列から求めるＰＡＴを高速に探索する
ため、ＰＡＴと較べるＳ(t)の長さを最大にし、ゲート
の遅延を最少化するためＰＡＴと較べるＳ(t)の長さを
最少化しなければならない。そのため、Ｓ(t)をＳ(t)＝
s1+s2・・・+si・・・+sk(length(si)＝n）に構成した後siと
ＰＡＴを並列処理を介して較べることにより前記条件を
全て満足することができる。もし、Ｓ(t)の長さがdであ
りＰＡＴの長さがnとした場合、d＝3nである場合の並列
処理パターンマッチングの構造を図３に示す。
【００４０】図３は入力ビット列をラッチ1,2,3 (30,3
1′,31″）とＰＬＡ-1,2,3 (31,31′,31″）に順次入力
させ、夫々のＰＬＡ1,2,3 (31,31′,31″）で前記固定
した移動量を有するパターン処理方法と類似するが、Ｐ
ＬＡ-1 (31）では以前の入力ビット列の順方向マッチ数
と現在入力された逆方向マッチ数を合せてマッチパター
ンのビット数と一致するか否かを検索し、ＰＬＡ-2 (3
1′）ではＰＬＡ-1 (31）で出力された順方向マッチ数
と入力ビット列の逆方向マッチ数を合せてマッチパター
ンのビット数と一致するか否か検索し、ＰＬＡ-3 (3
1″）ではＰＬＡ-2 (31′）で出力された順方向マッチ
数と入力ビット列の逆方向マッチ数を合せてマッチパタ
ーンのビット数と一致するか否かを検索する。このよう
に、前記ＰＬＡ-1,2,3 (31,31′,31″）でマッチパター
ンのビット数と一致するか否かを検索し、ＰＬＡ-3 (3
1″）の順方向マッチ数をレジスター (３２）に貯蔵さ
せた後、レジスター (３２）に貯蔵したものをＰＬＡ-1
(31）に出力されるようにし次に入力する入力ビット列
と関連されるようにする。即ち、前記ＰＬＡ-1,2,3 (3
1,31′,31″）を一つのＰＬＡと見れば、前記図２及び
表５に示す固定された移動量を有するパターンマッチン
グ処理と同様である。前記ＰＬＡ-1,2,3 (31,31′,3
1″）でパターン発見信号とシフトすべきビット数をシ
フトの和ＰＬＡ (３３）に伝え、シフトの和ＰＬＡ (３
５）の出力を制御部 (３３）とベラルシフト (３５）に
出力する。前記ベラルシフト (３５）では入力ビット列
とＰＬＡ-3 (31″）で連結されるラッチ (３６）から出
力する以前の入力ビット列でシフトの和ＰＬＡ (３３）
から出力するシフトすべきビット数だけシフトされるよ
うにする。なお、各ラッチのパターン発見信号により探
索するパターンの位置が相違することになる。そのた
め、それの計算にＰＬＡを用いる。そして、その結果は
制御部に伝える。Ｓ(t)の最終段ラッチでの順方向マッ
チ数をレジスターに貯蔵し、次の入力Ｓ(t+1)に最初に
くる入力ビット数と較べパターンマッチングか否かを制
御部に伝えることになる。この構造は入力ビット列Ｓの
長さLがマッチ パターンＰＡＴの長さnに較べ非常に長
く (L＞＞n）、またマッチパターンＰＡＴが入力ビット
列で存在する確立が非常に少ない場合、高速に求めるパ
ターンを探索する時は非常に有用である。このアルゴリ
ズムは前記で説明したように比較演算数は0(n)、回路の
複雑度は0(n)、クリティカルパス (critical path）0
(1)に増加する反面、ＰＡＴの最大移動量は0(n)増加す
る。そのため、HDテレビジョンのような同期化符号を探
索するシステムにおいて、一つの状態の時間を最少に維
持しながら回路の複雑度を0(n)の関数に増加させパター
ンを探索する速度を0(n)に高速化することができる。
1′,31″）とＰＬＡ-1,2,3 (31,31′,31″）に順次入力
させ、夫々のＰＬＡ1,2,3 (31,31′,31″）で前記固定
した移動量を有するパターン処理方法と類似するが、Ｐ
ＬＡ-1 (31）では以前の入力ビット列の順方向マッチ数
と現在入力された逆方向マッチ数を合せてマッチパター
ンのビット数と一致するか否かを検索し、ＰＬＡ-2 (3
1′）ではＰＬＡ-1 (31）で出力された順方向マッチ数
と入力ビット列の逆方向マッチ数を合せてマッチパター
ンのビット数と一致するか否か検索し、ＰＬＡ-3 (3
1″）ではＰＬＡ-2 (31′）で出力された順方向マッチ
数と入力ビット列の逆方向マッチ数を合せてマッチパタ
ーンのビット数と一致するか否かを検索する。このよう
に、前記ＰＬＡ-1,2,3 (31,31′,31″）でマッチパター
ンのビット数と一致するか否かを検索し、ＰＬＡ-3 (3
1″）の順方向マッチ数をレジスター (３２）に貯蔵さ
せた後、レジスター (３２）に貯蔵したものをＰＬＡ-1
(31）に出力されるようにし次に入力する入力ビット列
と関連されるようにする。即ち、前記ＰＬＡ-1,2,3 (3
1,31′,31″）を一つのＰＬＡと見れば、前記図２及び
表５に示す固定された移動量を有するパターンマッチン
グ処理と同様である。前記ＰＬＡ-1,2,3 (31,31′,3
1″）でパターン発見信号とシフトすべきビット数をシ
フトの和ＰＬＡ (３３）に伝え、シフトの和ＰＬＡ (３
５）の出力を制御部 (３３）とベラルシフト (３５）に
出力する。前記ベラルシフト (３５）では入力ビット列
とＰＬＡ-3 (31″）で連結されるラッチ (３６）から出
力する以前の入力ビット列でシフトの和ＰＬＡ (３３）
から出力するシフトすべきビット数だけシフトされるよ
うにする。なお、各ラッチのパターン発見信号により探
索するパターンの位置が相違することになる。そのた
め、それの計算にＰＬＡを用いる。そして、その結果は
制御部に伝える。Ｓ(t)の最終段ラッチでの順方向マッ
チ数をレジスターに貯蔵し、次の入力Ｓ(t+1)に最初に
くる入力ビット数と較べパターンマッチングか否かを制
御部に伝えることになる。この構造は入力ビット列Ｓの
長さLがマッチ パターンＰＡＴの長さnに較べ非常に長
く (L＞＞n）、またマッチパターンＰＡＴが入力ビット
列で存在する確立が非常に少ない場合、高速に求めるパ
ターンを探索する時は非常に有用である。このアルゴリ
ズムは前記で説明したように比較演算数は0(n)、回路の
複雑度は0(n)、クリティカルパス (critical path）0
(1)に増加する反面、ＰＡＴの最大移動量は0(n)増加す
る。そのため、HDテレビジョンのような同期化符号を探
索するシステムにおいて、一つの状態の時間を最少に維
持しながら回路の複雑度を0(n)の関数に増加させパター
ンを探索する速度を0(n)に高速化することができる。
【００４１】このアルゴリズムを高鮮明テレビジョンの
ビット列復号機に適用する。高鮮明テレビジョンのビッ
ト列復号機には、ビット列調査、同期化符号の探索、固
定長さ符号の復号及び各種の可変長さ符号の復号機能を
有する可変長さ復号機を有する。図４のようなハードウ
ェアの構造が一般に多く用いられる。ラッチ (１１）は
復号すべきビット列を貯蔵し、ベラルシフト (１２）は
現在復号すべき固定ビットを出力させる。ＰＬＡ (１
３）は現在復号したシンボルの符号の長さ及び復号した
シンボル値、また、同期化符号のマッチング及びVLC符
号の符号本 (codebook）との整合を示すパターン発見信
号を出する。累算機 (１４）は復号されたシンボルの符
号の長さを蓄積してベラルシフト (１２）が次の状態で
移動する量を決定する。
ビット列復号機に適用する。高鮮明テレビジョンのビッ
ト列復号機には、ビット列調査、同期化符号の探索、固
定長さ符号の復号及び各種の可変長さ符号の復号機能を
有する可変長さ復号機を有する。図４のようなハードウ
ェアの構造が一般に多く用いられる。ラッチ (１１）は
復号すべきビット列を貯蔵し、ベラルシフト (１２）は
現在復号すべき固定ビットを出力させる。ＰＬＡ (１
３）は現在復号したシンボルの符号の長さ及び復号した
シンボル値、また、同期化符号のマッチング及びVLC符
号の符号本 (codebook）との整合を示すパターン発見信
号を出する。累算機 (１４）は復号されたシンボルの符
号の長さを蓄積してベラルシフト (１２）が次の状態で
移動する量を決定する。
【００４２】伝達誤謬が入力ビット列に発生し、ＰＬＡ
のVLC符号がVLC符号のコードブックの符号と一致しない
場合にはマッチング信号では０値を出力する。制御シー
ケンス部では同期化符号を探索するモードに入れなが
ら、前記説明した同期パターンを探索するアルゴ リズ
ムで同期パターンを探索する。MPEGを基本アルゴ リズ
ムに利用した高鮮明テレビジョン圧縮アルゴリズムで
は、同期化符号で24bitを用いこのビット中、最初のビ
ットから23ビットまでは０であり、24番目のビットは１
である。そのため、前述の23ビットの０ビットは周期が
１のビット列である。そのため、再同期符号を探索する
ためには１のみ検出すると24番目のビットに１と０を区
別することができるロジック一つがさらに必要となる。
ベラルシフト (48bit input,32bit output）が最大16ビ
ットまで移動可能であれば入力ビット列の最大移動量は
16である。この時、パターンマッチの出力値とベラルシ
フトの入力値を表６に示す。表６でロジックを示し図４
の可変長さ符号化部構造のＰＬＡの中に入れコントロー
ルすると高速に再同期可能である。
のVLC符号がVLC符号のコードブックの符号と一致しない
場合にはマッチング信号では０値を出力する。制御シー
ケンス部では同期化符号を探索するモードに入れなが
ら、前記説明した同期パターンを探索するアルゴ リズ
ムで同期パターンを探索する。MPEGを基本アルゴ リズ
ムに利用した高鮮明テレビジョン圧縮アルゴリズムで
は、同期化符号で24bitを用いこのビット中、最初のビ
ットから23ビットまでは０であり、24番目のビットは１
である。そのため、前述の23ビットの０ビットは周期が
１のビット列である。そのため、再同期符号を探索する
ためには１のみ検出すると24番目のビットに１と０を区
別することができるロジック一つがさらに必要となる。
ベラルシフト (48bit input,32bit output）が最大16ビ
ットまで移動可能であれば入力ビット列の最大移動量は
16である。この時、パターンマッチの出力値とベラルシ
フトの入力値を表６に示す。表６でロジックを示し図４
の可変長さ符号化部構造のＰＬＡの中に入れコントロー
ルすると高速に再同期可能である。
【００４３】
【表６】
【００４４】前記の場合は、VLDを用い再同期を探索す
る可変長さ移動量を有する再同期アルゴ リズムを示す
ものである。しかし、VLDを用いず固定長さ移動量を有
する並列処理パターン マッチングを用いVLDの外部で高
速に再同期符号を探索した後で、この信号をVLDに伝え
る再同期アルゴ リズムを検討してみる。この時、ハー
ドウェア構成図は図３で説明した構成図と同一であり、
ＰＬＡの構造はVLDを用いたハードウェアの構造以前の
順方向マッチ数を追加して構成する。図５は、このアル
ゴリズムを高鮮明テレビジョンに応用した場合の全体構
成図を示している。図５でＳ(t)の長さはMPEGを基本と
するアルゴリズムと仮定すれば、再同期信号の長さは24
ビットとなる。各ラッチの入力は24ビットに固定させ
た。この長さの３倍である72bitをＳ(t)の長さとし、マ
ッチパターンが発見された場合、このマッチパターンの
移動量を計算しVLDに伝える回路がさらに必要でありこ
れをシフトの和ＰＬＡに示した。制御部は可変符号復号
機に再び入力バッファから入力ビット列を受け取るよう
命令する。この時、制御部は入力バッファで復号が始ま
るビットの位置をレジスターＡの情報から可変符号復号
機に知らせて再同期がなされるようにする。
る可変長さ移動量を有する再同期アルゴ リズムを示す
ものである。しかし、VLDを用いず固定長さ移動量を有
する並列処理パターン マッチングを用いVLDの外部で高
速に再同期符号を探索した後で、この信号をVLDに伝え
る再同期アルゴ リズムを検討してみる。この時、ハー
ドウェア構成図は図３で説明した構成図と同一であり、
ＰＬＡの構造はVLDを用いたハードウェアの構造以前の
順方向マッチ数を追加して構成する。図５は、このアル
ゴリズムを高鮮明テレビジョンに応用した場合の全体構
成図を示している。図５でＳ(t)の長さはMPEGを基本と
するアルゴリズムと仮定すれば、再同期信号の長さは24
ビットとなる。各ラッチの入力は24ビットに固定させ
た。この長さの３倍である72bitをＳ(t)の長さとし、マ
ッチパターンが発見された場合、このマッチパターンの
移動量を計算しVLDに伝える回路がさらに必要でありこ
れをシフトの和ＰＬＡに示した。制御部は可変符号復号
機に再び入力バッファから入力ビット列を受け取るよう
命令する。この時、制御部は入力バッファで復号が始ま
るビットの位置をレジスターＡの情報から可変符号復号
機に知らせて再同期がなされるようにする。
【００４５】
【発明の効果】前記のように、本発明によれば、VLＳI
技術の発達と共に従来実現が困難であった高速アルゴリ
ズムも実現することが可能である可能である。また、前
記した本発明は、高鮮明テレビジョン、マルチメディ
ア、B-IＳDN端末機等高速の演算処理を要求する各種デ
ィジタル信号を用いる全てのシステムに適用し得るた
め、その波及効果が非常に大きいものと期待される。
技術の発達と共に従来実現が困難であった高速アルゴリ
ズムも実現することが可能である可能である。また、前
記した本発明は、高鮮明テレビジョン、マルチメディ
ア、B-IＳDN端末機等高速の演算処理を要求する各種デ
ィジタル信号を用いる全てのシステムに適用し得るた
め、その波及効果が非常に大きいものと期待される。
【図１】 本発明の第１実施例により伝送誤謬が発生し
た可変長さ符号ビット列で同期信号を探索するようにし
た構成図。
た可変長さ符号ビット列で同期信号を探索するようにし
た構成図。
【図２】 本発明の第２実施例により伝送誤謬が発生し
た可変長さ符号ビット列で同期信号を探索するようにし
た構成図。
た可変長さ符号ビット列で同期信号を探索するようにし
た構成図。
【図３】 本発明の第３実施例により伝送誤謬が発生し
た可変長さ符号ビット列で高速に同期信号を探索するよ
う並列処理する構成図。
た可変長さ符号ビット列で高速に同期信号を探索するよ
う並列処理する構成図。
【図４】 高鮮明テレビジョンで可変長さ復号化部に本
発明の第１実施例に適用した例を示す構成図。
発明の第１実施例に適用した例を示す構成図。
【図５】 高鮮明テレビジョンで可変長さ復号化部に本
発明の第３実施例に適用した例を示す構成図。
発明の第３実施例に適用した例を示す構成図。
【符号の説明】 １０ 入力バッファ １１，２０，２１，２６，３０，３６ ラッチ １２ ベラルシフト １３ ＰＬＡ １４ 累算機 ２４ レジスター ２５ 制御部
───────────────────────────────────────────────────── フロントページの続き (51)Int.Cl.6 識別記号 庁内整理番号 ＦＩ 技術表示箇所 Ｈ０４Ｌ 7/08 Ａ
Claims (8)
- 【請求項１】 高鮮明テレビジョン、ディジタル テレ
ビジョン、マルチメディアステム等における可変長さ符
号に伝送誤謬が発生した場合、伝送したビット列を復旧
するための同期符号を探索方法であって、可変長さ移動
量をもって入力される入力ビット列から高速に同期符号
を探索するものにおいて、 ビット列でｎ＋１個の単位ビットで入力されるビット列
をＰＬＡに伝え、入力ビット列の同期符号とマッチする
パターンを探索するために、入力ビット列に対して同期
符号パターンを１ビットずつ順次シフトさせ入力ビット
列と夫々並列比較してパターンマッチが可能か否かを較
べ、パターンマッチが発見されなければパターンマッチ
になるまで累算機に入力された数に応じて次に連結する
入力ビット列を前記ＰＬＡに伝える一方、パターンマッ
チが発見されると前記ＰＬＡよりパターン発見信号を制
御部に送り、累算機に入力した前記パターンマッチにな
るまでのビット数をベラルシフトに送り、ベラルシフト
で前記ビット数ほど入力ビット数がシフトされるように
して、同期符号を入力ビット列で正確に探索可能とした
ことを特徴とする、並列処理パターンマッチングを用い
た可変長さ符号の高速再同期方法。 - 【請求項２】 高鮮明テレビジョン、ディジタル テ
レビジョン、マルチメディアステム等における可変長さ
符号に伝送誤謬が発生した場合、伝送したビット列を復
旧するための同期符号を探索方法であって、可変長さ移
動量をもって入力される入力ビット列から高速に同期符
号を探索するものにおいて、 入力ビット列を固定した長さに応じて、移動量をもって
入力されるビット列で同期符号を高速に探索するため
に、Ｎ＋１個のビットを有する単位入力ビット列をＰＬ
Ａに伝え、入力ビット列で同期符号とマッチする位置を
探索するため入力ビット列に対し同期符号のパターンを
１ビットずつ順次シフトするよう多数の同期符号パター
ンと入力ビット列とを夫々並列比較して順方向マッチ数
をレジストに貯蔵し、入力ビット列に対し同期符号パタ
ーンが１ビットずつ逆順にシフトされるようにした多数
個の同期符号パターンを、入力ビット列と夫々並列比較
して得た逆方向マッチ数と以前の単位ビット列で検索し
てレジストに貯蔵していた順方向マッチ数との和が同期
符号パターンのビット数と一致するか否かを探索する段
階と、 上記入力ビット列と夫々並列比較して得た逆方向マッチ
数と以前の単位ビット列で検索してレジストに貯蔵して
いた順方向マッチ数との和が同期符号パターンのビット
数が不一致の場合、一致するまで次の単位入力ビット列
を前記ＰＡＬに伝えられるようにし、上記操作を続ける
段階と、 上記入力ビット列と夫々並列比較して得た逆方向マッチ
数と以前の単位ビット列で検索してレジストに貯蔵して
いた順方向マッチ数との和が同期符号パターンのビット
数が一致した場合、パターン発見信号を制御部に送ると
共にシフトされる数をベラルシフトに伝える段階と、 前記ベラルシフトに、以前の単位入力ビット列と現在の
単位入力が夫々入力されるようにして前記シフトされる
数を入力する際、以前の単位入力ビット列と現在の単位
入力ビット列でシフトされるようにし入力ビット列で正
確な同期符号を探索して、伝送誤謬が発生したビット列
で同期符号を探索する段階とを備えたことを特徴とす
る、並列処理パターン マッチングを用いた可変長さ符
号の高速再同期方法。 - 【請求項３】 前記順方向マッチ数は、Ｎ＋１個の同期
符号パターンを入力ビット列と夫々並列比較し入力ビッ
ト列と同期符号パターンが一部分でもマッチする部分の
ビット数を検出することを特徴とする、請求項２に記載
の平行処理パターン マッチングを用いた可変長さ符号
の高速再同期方法。 - 【請求項４】 前記逆方向マッチ数は、入力ビット列に
対し同期符号パターンが１ビットずつ逆順にシフトされ
るようにした多数個の同期符号パターンを、入力ビット
列と夫々並列比較し入力ビット列と同期符号パターンが
一部分でもマッチする部分のビット数を検出することを
特徴とする、請求項２に記載の並列処理パターン マッ
チングを用いた可変長さ符号の高速再同期方法。 - 【請求項５】 前記ベラルシフトには、以前の単位入力
ビット列と現在の単位入力ビット列でシフトされるよう
にする動作は制御部で制御信号を受けて行うことを特徴
とする、請求項２に記載の並列処理パターン マッチン
グを用いた可変長さ符号の高速再同期方法。 - 【請求項６】 高鮮明テレビジョン、ディジタル テレ
ビジョン、マルチメディアステム等における可変長さ符
号に伝送誤謬が発生した場合、伝送したビット列を復旧
するための同期符号を探索方法において、 入力ビット列を固定した長さほど移動量をもって入力さ
れるビット列で、高速に同期符号を探索するため固定し
た長さを有する単位入力ビット列を多数個受け入れる段
階と、 夫々受け入れられた単位入力ビット列に対し同期符号が
一致する順方向マッチ数と、前記単位入力ビット列の直
前段階単位入力ビット列に対し同期符号が一致する逆方
向マッチ数を合せた同期符号パターンのビット数とが一
致するか否かを探索する段階と、 上記単位入力ビット列に対し同期符号が一致する順方向
マッチ数と、前記単位入力ビット列の直前段階単位入力
ビット列に対し同期符号が一致する逆方向マッチ数を合
せた同期符号パターンのビット数とが不一致の場合、一
致するまで次の多数の単位入力ビット列を受け入れるよ
うにし、前記のような作業を続ける段階と、 上記単位入力ビット列に対し同期符号が一致する順方向
マッチ数と、前記単位入力ビット列の直前段階単位入力
ビット列に対し同期符号が一致する逆方向マッチ数を合
せた同期符号パターンのビット数とが一致した場合、パ
ターン発見信号を総合し制御部に送ると共にシフトされ
る数をベラル シフトに伝える段階と、 前記ベラルシフトには、以前に入力した最終番目の単位
入力ビット列と、現在の単位入力が全て入力されるよう
にし、前記シフトされる数を入力する以前の単位入力ビ
ット列と、現在の単位入力ビット列でシフトされるよう
にして入力ビット列で同期符号を探索することを特徴と
する、並列処理パターンマッチングを用いた可変長さ符
号の高速再同期方法。 - 【請求項７】 前記順方向マッチ数は、同期符号パター
ンを入力ビット列に対し１ビットずつ順次シフトさせ夫
々並列比較した入力ビット列と、同期符号パターンが一
部分でもマッチする部分のビット数を検出することを特
徴とする、請求項６記載の並列処理パターンマッチング
を用いた可変長さ符号の高速再同期方法。 - 【請求項８】 前記逆方向マッチ数は、入力ビット列に
対し同期符号パターンが１ビットずつ逆順シフトされる
ようにした多数個の同期符号パターンを入力ビット列と
夫々並列比較し、入力ビット列と同期符号パターンが一
部分でもマッチする部分のビット数を検出することを特
徴とする、請求項６記載の並列処理パターン マッチン
グを用いた可変長さ符号の高速再同期方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| KR1019940003769A KR970003024B1 (ko) | 1994-02-28 | 1994-02-28 | 병렬처리 패턴매칭을 이용한 가변부호길이에서 고속 재동기방법 |
| KR1994-3769 | 1994-02-28 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH089371A true JPH089371A (ja) | 1996-01-12 |
Family
ID=19378019
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP4091495A Pending JPH089371A (ja) | 1994-02-28 | 1995-02-28 | 並列処理パターンマッチングを用いた可変長さ符号の高速再同期方法 |
Country Status (3)
| Country | Link |
|---|---|
| US (1) | US5625356A (ja) |
| JP (1) | JPH089371A (ja) |
| KR (1) | KR970003024B1 (ja) |
Families Citing this family (17)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP0731614B1 (en) * | 1995-03-10 | 2002-02-06 | Kabushiki Kaisha Toshiba | Video coding/decoding apparatus |
| DE69624276T2 (de) * | 1995-03-15 | 2003-06-12 | Kabushiki Kaisha Toshiba, Tokio/Tokyo | System und Verfahren zur variablen Längenkodierung von sich bewegenden Bildern |
| US6104754A (en) * | 1995-03-15 | 2000-08-15 | Kabushiki Kaisha Toshiba | Moving picture coding and/or decoding systems, and variable-length coding and/or decoding system |
| US6704494B1 (en) * | 1995-03-15 | 2004-03-09 | Kabushiki Kaisha Toshiba | Moving picture coding and/or decoding systems, and variable-length coding and/or decoding system |
| JP2809126B2 (ja) * | 1995-03-30 | 1998-10-08 | 日本電気株式会社 | 音声信号処理回路および音声信号処理方法 |
| KR100192269B1 (ko) * | 1996-03-25 | 1999-06-15 | 구자홍 | 가변길이 코드 디코더 |
| US5870039A (en) * | 1996-06-19 | 1999-02-09 | Matsushita Electric Industrial Co., Ltd. | Code converter, variable length code decoder, and associated methods |
| KR100292050B1 (ko) * | 1997-11-08 | 2001-06-01 | 김영환 | 가변장복호기의 데이타 가변장치 |
| US6934338B1 (en) | 1998-05-18 | 2005-08-23 | Sony Corporation | Variable length decoder for decoding digitally encoded video signals |
| US6704361B2 (en) | 1998-05-18 | 2004-03-09 | Sony Corporation | Variable length decoder for decoding digitally encoded video signals |
| IT1308456B1 (it) * | 1999-04-26 | 2001-12-17 | Olivetti Lexikon Spa | Dispositivo per comprimere/decomprimere stringhe di bit |
| US7526804B2 (en) * | 2004-02-02 | 2009-04-28 | Microsoft Corporation | Hardware assist for pattern matches |
| US20080148044A1 (en) * | 2006-12-19 | 2008-06-19 | Motorola, Inc. | Locking carrier access in a communication network |
| WO2008109790A1 (en) * | 2007-03-07 | 2008-09-12 | Marvell International Ltd. | Codebook selection for transmit beamforming |
| US8942306B2 (en) | 2007-03-07 | 2015-01-27 | Marvell World Trade Ltd. | Codebook selection for transmit beamforming |
| US9300371B1 (en) | 2008-03-07 | 2016-03-29 | Marvell International Ltd. | Beamforming systems and methods |
| US8638875B1 (en) | 2008-04-15 | 2014-01-28 | Marvell International Ltd. | Transmit beamforming systems and methods |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH049342A (ja) * | 1990-04-26 | 1992-01-14 | Hitachi Chem Co Ltd | パーフルオロアルキルデユレンの製造法 |
| JPH05122676A (ja) * | 1991-10-28 | 1993-05-18 | Matsushita Electric Ind Co Ltd | 映像デイジタル伝送装置 |
Family Cites Families (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US3971888A (en) * | 1975-04-02 | 1976-07-27 | Bell Telephone Laboratories, Incorporated | Synchronization system for variable length encoded signals |
| GB9004188D0 (en) * | 1990-02-23 | 1990-04-18 | Plessey Telecomm | Method and apparatus for detecting a frame alignment word in a data stream |
| US5299236A (en) * | 1992-11-13 | 1994-03-29 | Toshiba America Information Systems, Inc. | System and method for obtaining and maintaining synchronization of a demodulated signal |
-
1994
- 1994-02-28 KR KR1019940003769A patent/KR970003024B1/ko not_active Expired - Fee Related
-
1995
- 1995-02-28 US US08/395,713 patent/US5625356A/en not_active Expired - Lifetime
- 1995-02-28 JP JP4091495A patent/JPH089371A/ja active Pending
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH049342A (ja) * | 1990-04-26 | 1992-01-14 | Hitachi Chem Co Ltd | パーフルオロアルキルデユレンの製造法 |
| JPH05122676A (ja) * | 1991-10-28 | 1993-05-18 | Matsushita Electric Ind Co Ltd | 映像デイジタル伝送装置 |
Also Published As
| Publication number | Publication date |
|---|---|
| KR970003024B1 (ko) | 1997-03-13 |
| KR950026262A (ko) | 1995-09-18 |
| US5625356A (en) | 1997-04-29 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH089371A (ja) | 並列処理パターンマッチングを用いた可変長さ符号の高速再同期方法 | |
| JP3136796B2 (ja) | 可変長符号デコーダ | |
| US5771010A (en) | Apparatus for compressing data using a Lempel-Ziv-type algorithm | |
| US5148271A (en) | Method for transmission of variable length code and apparatus for coding a video signal | |
| US6215424B1 (en) | System for variable length codeword processing suitable for video and other applications | |
| EP0439569B1 (en) | Apparatus for run and string data compression | |
| US6043765A (en) | Method and apparatus for performing a parallel speculative Huffman decoding using both partial and full decoders | |
| KR19980702512A (ko) | 가변 길이 디코더 | |
| US7487423B2 (en) | Decoding method, medium, and apparatus | |
| JPH11266162A (ja) | 符号化方法、符号化装置、圧縮／伸長システム、ｆｓｍコ―ダ―及びコ―ダ― | |
| US4990910A (en) | Variable length code conversion system | |
| EP0802681B1 (en) | Variable length code decoder | |
| US5432512A (en) | Apparatus for decoding variable length codes | |
| US5701126A (en) | High speed variable length decoder | |
| KR100466455B1 (ko) | 부호변환기와가변길이부호복호장치및복호방법 | |
| US6084925A (en) | Method and apparatus for discriminating synchronous or asynchronous states of Viterbi decoded data | |
| JPH0779165A (ja) | 可変長復号化装置 | |
| US6707396B2 (en) | Device and method for parallel processing implementation of bit-stuffing/unstuffing and NRZI-encoding/decoding | |
| CN101547353B (zh) | 可变长码解码加速装置 | |
| KR100223043B1 (ko) | 고정된 길이의 이동량을 갖는 패턴매칭 판별방법 및 그 장치 | |
| JP2000209100A (ja) | デコ―ダ及びデコ―ド方法 | |
| TW202531710A (zh) | 具有零累積誤差的計數系統及其驅動方法 | |
| JP3128016B2 (ja) | 画像圧縮装置 | |
| JP3351732B2 (ja) | 算術符号化装置および方法、算術復号装置および方法、並びに記録媒体 | |
| KR0125125B1 (ko) | 고속 가변길이부호 복호화 장치 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A02 | Decision of refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A02 Effective date: 19991130 |