[go: up one dir, main page]

JPH04252329A - データを可変長ビットパターンで表す方法及び通信システム - Google Patents

データを可変長ビットパターンで表す方法及び通信システム

Info

Publication number
JPH04252329A
JPH04252329A JP3082006A JP8200691A JPH04252329A JP H04252329 A JPH04252329 A JP H04252329A JP 3082006 A JP3082006 A JP 3082006A JP 8200691 A JP8200691 A JP 8200691A JP H04252329 A JPH04252329 A JP H04252329A
Authority
JP
Japan
Prior art keywords
bit
patterns
data
bits
pattern
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
Application number
JP3082006A
Other languages
English (en)
Inventor
Eugene I Barzach
ユージーン　アイ．バルザック
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
RTX Corp
Original Assignee
United Technologies Corp
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by United Technologies Corp filed Critical United Technologies Corp
Publication of JPH04252329A publication Critical patent/JPH04252329A/ja
Pending legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/40—Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Compression, Expansion, Code Conversion, And Decoders (AREA)
  • Communication Control (AREA)

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明は、電子通信の分野に係り
、特に、データ表示用に可変長２進ビットパターンを採
用している電子通信分野に関する。
【０００２】
【従来の技術】情報は、ビットパターンを形成するよう
に一緒にグループ化される一連の２進値（すなわち、１
と０の組合せ）によって表現され得る。
【０００３】多くのビットパターンは、結合により集合
を形成し、表現されようとしている情報に対して１対１
に割り当てられる。例えば、ＡＳＣＩＩ（アスキー）ビ
ットパターン集合は、文字、数字、及び記号を表すため
のビットパターンを含み、そこでは、各唯一のビットパ
ターンが唯一の文字、数字、あるいは記号を表している
。
【０００４】もっとも簡単な型のビットパターン集合は
、一定数のビットを持つ集合内に全てのビットパターン
を有する。しかし、各唯一のビットパターンが唯一のデ
ータ要素を表すために用いられる場合や、特定のデータ
要素の発生確率が他の特定データ要素の発生確率と異な
る場合には、データ表現効率の増大（すなわち、ビット
数に表わされた情報の比率の増大）は、可変長ビットパ
ターンを採用することによって、さらに、より大きなビ
ット数を持つパターンを発生確率の低いデータ要素に割
り当てることによって、達成される。例えば、英文を形
成するために使用されるアルファベットの文字を符号化
するために、可変長ビットパターン集合が採用されると
すると、最も頻繁に発生する文字「Ｅ」は、最も小さな
ビット数を持つパターンに割り当てられる。一方、最も
発生頻度の小さい文字「Ｚ」は、最も大きなビット数を
持つパターンに割り当てられる。
【０００５】
【発明が解決しようとする課題】可変長ビットパターン
集合を採用するに当たっての１つの困難性は、直列ビッ
ト流内で隣接して発生する比較的短いパターン（直列ビ
ット流は、コンピュータ間の通信に特に使用される）が
、結合され、他のより長いパターンと同一のパターンを
形成することがあるということである。例えば、文字「
Ｅ」を表すためにビットパターン「１１」が、文字「Ａ
」を表すためにビットパターン「００」が、そして文字
「Ｓ」を表すためにビットパターン「１１００」が用い
られたとすると、そのビット流「１１００」は、文字「
ＥＡ」または文字「Ｓ」のいずれも表すため、意味が曖
昧となる。
【０００６】その集合内にビットパターンのいずれかの
組み合わせの連結によって形成され得るパターンを含ま
ない可変長ビットパターンの集合を採用することによっ
て避けることができる。例えば、「誤り伝幡制限による
ランレングス制限可変長コード化」（Ｆｒａｎａｓｚｅ
ｋ）と題する米国特許第３，６８９，８９９号では、分
割パターン間を明確に区別することができるように、唯
一のビットシーケンスを各ビットパターンの終わりに添
付するような複雑な構成を採用することによって曖昧さ
を避けるようにしている。
【０００７】同様に、ハフマン符号では、単一の０で終
わるか、または最大パターン長であるビットパターンで
あってかつ残りのビット位置の全てに１を含むビットパ
ターンが用いられている。それらのパターンは、最後の
０によって、または全て１である最大数ビットを持つこ
とによって区別され得るため、曖昧さがない。例えば、
ハフマン符号の４個の要素集合は、次のビットパターン
すなわち０，１０，１１０，及び１１１から構成される
。
【０００８】その　’８９９号特許、ハフマン符号及び
他の可変長構成は、連結曖昧性の問題を解決するが、採
用される解決法では、ビットパターン集合内にある次の
パターンのビット数が、その集合のパターン数が増すに
従って実質的に増大する。例えば、Ｎ個のハフマン符号
の集合内の最長ビットパターンは、Ｎ−１ビットを有す
る。ビット数の増加は、可変長ビットパターンの使用目
的、すなわち、データ表現効率を増すために、データを
表すために採用される全ビット数を減少させるという目
的に反する。
【０００９】本発明の目的は、可変長ビットパターン集
合の構造及び使用を含み、そのビットパターンにおいて
は、その集合内のパターンが、その集合の１以上の他の
パターンを連結して形成されることがなく、かつ最長パ
ターンに含まれるビット数は、その集合内のパターン数
が増すに従って最小化される。
【００１０】
【課題を解決するための手段】本発明によれば、データ
を表すためのビットパターンの集合は、特定の２進値に
等しい最初のビットと最後のビットを持ち、かつ上記パ
ターンのそれぞれが、上記２進値に等しい単独のみに発
生するビットを持っている。
【００１１】
【実施例】図１を参照する。テーブル６は、１集合の可
変長ビットパターン７〜１４を表わしている。それらの
パターン７〜１４のそれぞれは、０に等しい最も重要な
ビット（最も左手）と、０に等しい最も重要でないビッ
ト（最も右手）を有する。また、パターン７〜１４のそ
れぞれは、０に等しい単独にのみ発生するビット（すな
わち、０に等しいビットに隣接して、０に等しい他のビ
ットが存在しない）を有する。０ビットで始まり０ビッ
トで終わるビットパターンであって、かつ単独にのみ発
生する０ビットを持つビットパターンの数は、無限に存
在することに留意されたい。従って、テーブル６に示さ
れるパターン７〜１４は、存在する。無限のそのような
パターン数の部分集合である。
【００１２】図１のパターン７〜１４は、アルファベッ
トの幾つかの文字に割り当てられ得る。パターン７は文
字「Ａ」に、パターン８は文字「Ｂ」に、パターン９は
文字「Ｃ」に、及びパターン１０は文字「Ｄ」に割り当
てられる。パターン７〜１０のビット数は変化するので
、文字「Ａ」の発生頻度が「Ｂ」のそれよりも大で、文
字「Ｂ」の発生頻度が、「Ｃ」のそれよりも大で、文字
「Ｃ」の発生頻度が「Ｄ」のそれよりも大である場合に
は、この割り当ては、データ表現効率を増大させる（す
なわち、ビット数当たりの情報の比率を増大させる）。
【００１３】図２は、上述の割り当て法が、ビット流１
５を構成するために採用され得ることを表わしている。 文字「ＡＢＣＤ」を表すビット流１５は、２個の分割パ
ターンが結合される場所ではどこでも、またその場所の
み２つの連続する０ビットを有する。この連続０ビット
現象は、１つだけの０ビットを含むパターン７が、２つ
の他のパターン間におかれた場合にも起こり得る。例え
ば、文字列「ＣＡＢ」を表すビット流は、０１１０００
１０となる。そのビット流内の第３番から第５番ビット
位置における３つの連続０ビットは、一対の連続する０
ビットとして考慮される。そこでは、そのビット流１５
は、可変長ビットパターンを含んでいるが、そのビット
流１５を複数のＮビット固定長パターンに分割し、各固
定長パターンを各メモリ分割に記憶することにより、Ｎ
ビットの長い固定長データ分割を有するデータメモリ内
にビット流１５を記憶することが可能である。
【００１４】図３を参照する。通信システム１６は、送
信機１７、通信路１９、及び受信機２１から構成されて
いる。データは、外部のデータ源（図示せず）から送信
機１７に（当業者に知られた種々の手段によって）入力
され、通信路１９を介して受信機２１に渡される。通信
路１９は、単一の電気線、複数の電気線、電話回線、ま
たは当業者に知られた他の信号導通媒体であっても良い
。
【００１５】送信機１７は、第１のデータ割当器２３及
び信号ドライバ２５から構成されている。データ割当器
２３は、入力ビットパターンを、０に等しい最も重要な
及び最も重要でないビットを有し、かつ単独にのみ発生
する０ビットを有する可変長ビットパターンに変換し、
その後上記可変長ビットパターンを連続して、単一ビッ
ト流にする。入力ビットパターンを上記可変長ビットパ
ターンを含んでいるビット流に変換するために、データ
割当器２３は、周知の方法で、ＲＯＭ（読出し専用メモ
リ）ルックアップテーブル（図示せず）を有するマイク
ロプロセッサを使用する。入力ビットパターンは、例え
ばアスキーなどのいかなるデータ構成であっても良い。 しかし、各唯一の入力ビットパターンに対して、唯一の
可変長ビットパターンが存在する。
【００１６】ビット流は、データ割当器２３から信号ド
ライバ２５へ出力される。信号ドライバ２５は、そのビ
ット流のビットを、通信路１９に使用される特定の媒体
に対して適切なフォーマットに変換する。例えば、通信
路１９が電話回線である場合には、信号ドライバ２５で
は、ビット流の各ビットに対して第１または第２階調を
出力する。ここで、第１階調は、０に等しいビットを表
し、第２階調は、１に等しいビットを表す。通信路１９
がファイバ光ケーブルの場合には、信号ドライバ２５は
、光出力パルスである。
【００１７】受信機２１は、信号バッファ２７と第２デ
ータ割当器２９から構成されている。信号バッファ２７
は、通信路１９を介して受信したビット流信号を、第２
データ割当器２９への入力に好適なフォーマットに変換
する。通信路１９が、ファイバ光リンクであり、第２デ
ータ割当器２９が、ディジタル装置である場合には、信
号バッファは、光信号をディジタル電気信号に変換する
。
【００１８】第２データ割当器２９は、ビット流を分離
可変長ビットパターンに分割し（２つの連結０ビットが
存在する場合）、その後、可変長ビットパターンのそれ
ぞれを、アスキーなどの出力データフォーマットに変換
する。第２データ割当器２９は、当業者に知られた方法
で、ＲＯＭロックアップテーブル（図示せず）を有する
マイクロプロセッサシステムを使用する。
【００１９】通信システム１６は、より頻繁に発生する
データが、上記したごとく、最も少ないビット数を有す
る可変長ビットパターンに応答するとき、効率的データ
スループット（すなわち、情報対ビット数の高い比率）
を達成する。通信路１９の使用コストが増すに従って、
その通信システムによって得られる効率は、より一層有
利になる。
【００２０】本発明では、ビットパターンが、最も重要
なビット位置及び最も重要でないビット位置において０
を有し、かつ単独でのみ発生する０ビットを有するもの
として説明されているが、ビットパターンが最も重要な
ビット位置及び最も重要でないビット位置において１ビ
ットを有し、かつ単独でのみ発生する１ビットを有する
ものであっても実施できる。
【００２１】通信システム１６は、通信路１９を介して
送信機１７と受信機２１の間でやり取りされる信号の型
に制限されない。データ割当器２３，２９は、ＲＯＭロ
ックアップテーブルを有するマイクロプロセッサを基本
とするシステムとして示されているが、当業者に知られ
ている如く、割当器２３，２９は種々の方法で構成され
得る。すなわち、その割当器は、必ずしもマイクロプロ
セッサやＲＯＭロックアップテーブルを必要としない。 通信システム１６へ入るデータ及びそこから出力される
データは、アスキーとして示されているが、そのシステ
ム１６は、どの様な型のデータを伝送するためにも使用
され得る。
【００２２】
【発明の効果】本発明によれば、可変長ビットパターン
の使用目的、すなわち、データ表現効率を増すために、
データを表すために採用される全ビット数を減少させる
という目的が達成される。
【図面の簡単な説明】
【図１】本発明に係るビットパターンのテーブルである
。
【図２】図１のビットパターンを用いて形成された見本
のビット流を示す図である。
【図３】本発明を採用している通信システムのブロック
図である。
【符号の説明】
６　　テーブル ７〜１４　　ビットパターン １５　　ビット流 １６　　通信システム １７　　送信機 １９　　通信路 ２１　　受信機 ２３，２９　　データ割当器 ２５　　信号ドライバ ２７　　信号バッファ

Claims (10)

    【特許請求の範囲】
  1. 【請求項１】　　データ要素の集合を表すために、ビッ
    トパターンの集合を用いる方法において、上記データ要
    素のそれぞれ唯一のものを上記ビットパターンの唯一の
    ものに割り当てるステップを有し、上記パターンのそれ
    ぞれが、特定の２進値に等しい最初のビットと最後のビ
    ットを持ち、かつ上記パターンのそれぞれが、上記２進
    値に等しい単独のみに発生するビットを持っていること
    を特徴とする方法。
  2. 【請求項２】　　請求項１に記載の方法において、上記
    特定の２進値が０であることを特徴とする方法。
  3. 【請求項３】　　請求項１に記載の方法において、上記
    特定の２進値が１であることを特徴とする方法。
  4. 【請求項４】　　請求項２に記載の方法において、上記
    組のデータ要素の内で最も頻繁に発生する要素が最も小
    さなビット数を持つビットパターンに割り当てられるこ
    とを特徴とする方法。
  5. 【請求項５】　　請求項３に記載の方法において、上記
    組のデータ要素の内で最も頻繁に発生する要素が最も小
    さなビット数を持つビットパターンに割り当てられるこ
    とを特徴とする方法。
  6. 【請求項６】　　入力データを、最初と最後のビットが
    特定の２進値に等しく、かつ単独にのみ発生するビット
    が上記２進値に等しい１組のビットパターンに変換する
    と共に、上記ビットパターンを連結してビット流にする
    ための第１のデータ割当器と、上記ビット流を送信する
    ための送信機と、上記ビット流を受信するための受信機
    と、上記ビット流を複数の可変長ビットパターンに分割
    すると共に、上記パターンを出力データに変換するため
    の第２のデータ割当器と、から構成される通信システム
    。
  7. 【請求項７】　　請求項６に記載の方法において、上記
    特定の２進値が０であることを特徴とする方法。
  8. 【請求項８】　　請求項６に記載の方法において、上記
    特定の２進値が１であることを特徴とする方法。
  9. 【請求項９】　　請求項７に記載の通信システムにおい
    て、上記入力データが、アスキー形態であることを特徴
    とする通信システム。
  10. 【請求項１０】　　請求項８に記載の通信システムにお
    いて、上記入力データが、アスキー形態であることを特
    徴とする通信システム。
JP3082006A 1990-03-22 1991-03-20 データを可変長ビットパターンで表す方法及び通信システム Pending JPH04252329A (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US497,271 1990-03-22
US07/497,271 US5034741A (en) 1990-03-22 1990-03-22 Variable length bit patterns for data representation

Publications (1)

Publication Number Publication Date
JPH04252329A true JPH04252329A (ja) 1992-09-08

Family

ID=23976154

Family Applications (1)

Application Number Title Priority Date Filing Date
JP3082006A Pending JPH04252329A (ja) 1990-03-22 1991-03-20 データを可変長ビットパターンで表す方法及び通信システム

Country Status (2)

Country Link
US (1) US5034741A (ja)
JP (1) JPH04252329A (ja)

Families Citing this family (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
FR2684822B1 (fr) * 1991-12-06 1994-03-25 Nicolas Vaugnier Procede et appareil pour convertir des codes reguliers en des codes de tailles variables et pour assurer la communication en serie des codes obtenus.
US5671377A (en) * 1994-07-19 1997-09-23 David Sarnoff Research Center, Inc. System for supplying streams of data to multiple users by distributing a data stream to multiple processors and enabling each user to manipulate supplied data stream
US6094453A (en) * 1996-10-11 2000-07-25 Digital Accelerator Corporation Digital data compression with quad-tree coding of header file
US7864471B2 (en) * 2008-07-24 2011-01-04 Seagate Technology Llc Converting timing errors into symbol errors to handle write mis-synchronization in bit-patterened media recording systems
NL2003311C2 (en) * 2009-07-30 2011-02-02 Intresco B V Method for producing a biological pin code.
US20150321903A1 (en) * 2013-03-15 2015-11-12 InvenSense, Incorporated System and method for hierarchical sensor processing

Family Cites Families (19)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US3051940A (en) * 1958-09-04 1962-08-28 Bell Telephone Labor Inc Variable length code group circuits
US3016527A (en) * 1958-09-04 1962-01-09 Bell Telephone Labor Inc Apparatus for utilizing variable length alphabetized codes
US3675212A (en) * 1970-08-10 1972-07-04 Ibm Data compaction using variable-length coding
US3675211A (en) * 1970-09-08 1972-07-04 Ibm Data compaction using modified variable-length coding
US3701111A (en) * 1971-02-08 1972-10-24 Ibm Method of and apparatus for decoding variable-length codes having length-indicating prefixes
US3716851A (en) * 1971-02-09 1973-02-13 Bell Telephone Labor Inc Self-synchronizing sequential encoding systems
US3717851A (en) * 1971-03-03 1973-02-20 Ibm Processing of compacted data
US3689899A (en) * 1971-06-07 1972-09-05 Ibm Run-length-limited variable-length coding with error propagation limitation
US4247891A (en) * 1979-01-02 1981-01-27 Honeywell Information Systems Inc. Leading zero count formation
JPS55141852A (en) * 1979-04-24 1980-11-06 Sony Corp Data converting system
US4396906A (en) * 1980-10-31 1983-08-02 Sri International Method and apparatus for digital Huffman encoding
US4463344A (en) * 1981-12-31 1984-07-31 International Business Machines Corporation Method and apparatus for generating a noiseless sliding block code for a (2,7) channel with rate 1/2
US4597057A (en) * 1981-12-31 1986-06-24 System Development Corporation System for compressed storage of 8-bit ASCII bytes using coded strings of 4 bit nibbles
JPS6069943A (ja) * 1983-09-26 1985-04-20 Sony Corp コ−ド変換方式
US4598326A (en) * 1983-10-18 1986-07-01 Honeywell Inc. Digital recording apparatus with disparity reducing encoder
EP0149893B1 (en) * 1983-12-08 1990-05-16 Crosfield Electronics Limited Apparatus for coding and decoding data
US4899149A (en) * 1986-02-28 1990-02-06 Gary Kahan Method of and apparatus for decoding Huffman or variable-length coees
US4675652A (en) * 1986-04-11 1987-06-23 Quantum Corporation Integrated encoder decoder for variable length, zero run length limited codes
US4882583A (en) * 1988-05-31 1989-11-21 International Business Machines Corporation Modified sliding block code for limiting error propagation

Also Published As

Publication number Publication date
US5034741A (en) 1991-07-23

Similar Documents

Publication Publication Date Title
CA2096176C (en) Variable length decoder
US7098817B2 (en) Methods and apparatus for constant-weight encoding and decoding
US5781129A (en) Adaptive encoder circuit for multiple data channels and method of encoding
US20030076248A1 (en) System and method for transmitting and storing data using an enhanced encoding scheme
JPS61212920A (ja) データ圧縮方法およびコード化された圧縮データの受信方法
EP0366938B1 (en) High speed switch as for an optical communication system
KR920011266A (ko) 디지탈 송수신 방법 및 장치
KR920018722A (ko) 개량된 블록 부호화에 의한 디지탈 신호의 부호화장치
US6642864B1 (en) Method and apparatus for encoding/decoding N-bit data into 2N-bit codewords
JPH04252329A (ja) データを可変長ビットパターンで表す方法及び通信システム
EP0905947A2 (en) Modulation/demodulation method and apparatus
HUP9902002A2 (hu) Berendezés m-bites adatszósorozat modulált jellé való átalakítására
US7071855B1 (en) Gray code conversion method and apparatus embodying the same
JP2818936B2 (ja) ２進データ処理方法および回路
US5729224A (en) Code conversion and demodulation apparatus, a method thereof, and a recording medium
JP2563239B2 (ja) 同期パタ−ン選定方法
JP3515526B2 (ja) 通信システムにおける制御情報の符号化方法
JP2537551B2 (ja) 可変長符号復号回路
RU117240U1 (ru) Устройство передачи и приема данных с использованием сигнала 4в3т
KR100322474B1 (ko) 다중화 방식을 이용한 고속신호 선로 부호화회로
JPS60167550A (ja) 符号変換装置
Usher Binary Coding in Noiseless Channels
KR20010096009A (ko) 통신 및 멀티미디어를 위한 변조코드
SU656053A1 (ru) Преобразователь двоичного кода в перестановочный код
JPS60194856A (ja) 付加信号伝送装置