Loading article…
Chen–Ho エンコーディングは、10 進数のバイナリエンコーディングのメモリ効率の高い代替システムです。
10進数の従来の2進符号化システムは、2進化10進数（BCD）として知られ、各桁を符号化するために4ビットを使用するため、パックBCDを使用する場合でも、バイナリデータ帯域幅が大幅に浪費されます（4ビットで16の状態を保存できるが、10の状態しか保存できないため）[1]。
このエンコードにより、基数変換などの複雑な算術演算を回避し、単純なブール変換のみを使用して、2 桁の 10 進数 (100 状態) のストレージ要件を 8 ビットから 7 ビットに、3 桁の 10 進数 (1000 状態) のストレージ要件を 12 ビットから 10 ビットに削減できます。
歴史
複数の発見があったと思われるが、後にChen-Ho符号化として知られるようになった概念のいくつかは、1969年にTheodore M. Hertz [2]と1971年にTien Chi Chen (陳天機) (1928–) [3] [4] [5] [6]によって独立して開発された。
ロックウェルのヘルツは1969年に彼の符号化方式の特許を申請し、1971年に認可された。[2]
陳は1971年に初めてアーヴィング・ツェ・ホー（Irving Tze Ho、1921–2003）[7] [8] [9] [10] と彼のアイデアについて議論した。陳とホーは当時、別の場所ではあったが、両者ともIBMで働いていた。 [11] [12]陳はまた、フランク・チン・トン[13]に相談し、彼の理論の結果を独自に検証した。[12] IBMは1973年に彼らの名前で特許を申請し、1974年に認可された。[14]少なくとも1973年までに、ハーツの以前の研究はIBMに知られていたに違いない、なぜならその特許は彼の特許を先行技術として引用しているからである。[14]
ジョセフ・D・ラトレッジとジョン・C・マクファーソンの協力を得て、[15]チェン・ホー符号化方式の最終版は1974年にIBM社内で配布され[16] 、1975年にCommunications of the ACM誌に掲載されました。[15] [17]このバージョンには、主に符号化システムの適用に関連するいくつかの改良点が含まれていました。これはハフマンのようなプレフィックスコードです。
この符号化方式は、1975年にはChenとHoの方式と呼ばれ、[18] 1982年にはChenの符号化方式と呼ばれ、[19] 2000年以降はChen–Ho符号化方式またはChen–Hoアルゴリズムとして知られるようになりました。 [17] 2001年に特許を申請した後、[20] Michael F. Cowlishawは、 2002年にIEE Proceedings – Computers and Digital Techniquesで、 Densely Packed Decimal (DPD)符号化方式として知られるChen–Ho符号化方式のさらなる改良を発表しました。[21] [22]その後、DPDはIEEE 754-2008およびISO/IEC/IEEE 60559:2011浮動小数点標準で使用される10進符号化方式として採用されました。
応用
チェンは、0 から 7 までの数字は、対応する8進数グループの 3 つの 2 進数字を使用して単純にエンコードされていると指摘しました。また、 1 ビットを使用してエンコードされる 8 と 9 の数字については、フラグを使用して異なるエンコードを識別できると仮定しました。
実際には、一連のブール変換が入力ビットのストリームに適用され、BCD エンコードされた数字が 3 桁あたり 12 ビットから 3 桁あたり 10 ビットに圧縮されます。逆の変換を使用して、結果のコード化されたストリームを BCD にデコードします。ルックアップ テーブルを使用して同等の結果を得ることもできます。
陳和符号化は、10進数3桁を10ビットのグループ（いわゆるデクレット）に符号化することに限られている。[1] 10ビットを使用することで可能な1024の状態のうち、未使用の状態は24状態のみとなる[1]（don't careビットは通常、書き込み時に0に設定され、読み取り時に無視される）。無駄はわずか2.34%で、1桁を4ビットで表すBCDよりも20%効率的な符号化となる。[12] [17]
ヘルツとチェンは、2桁の10進数（BCDでは8ビット必要）を7ビットのグループに圧縮する、同様の、しかし効率の悪い符号化方式も提案した。[2] [12]
より大きな10進数の数字は3桁と2桁のグループに分けられる。[2]
特許では、8-4-2-1 BCD [2]以外の10進コード、例えばExcess-3、[2] Excess-6、Jump-at-2、Jump-at-8、Gray、Glixon、O'Brien type-I、Gray–Stibitzコード[a]でエンコードされた数字にこの方式を適応させる可能性についても議論されています。同じ原理は他の基数にも適用できます。
1973年には、 IBM System/370 Model 165および370 Model 168コンピュータのオプションのIBM 7070/7074エミュレーション機能のアドレス変換ハードウェアに、何らかの形のChen-Hoエンコーディングが利用されていたようです。[23] [24]
ある有名なアプリケーションでは、128 ビット レジスタを使用して 3 桁の指数を持つ 33 桁の 10 進数を格納します。これは、バイナリ エンコーディングを使用して実現できる数値と実質的に同じです (BCD エンコーディングでは、同じ桁数を格納するのに 144 ビットが必要です)。
2桁の10進数のエンコーディング
ヘルツエンコーディング
- このエンコーディングはパリティを保持しません。
初期のChen-Ho符号化、方法A
- このエンコーディングはパリティを保持しません。
初期のChen-Ho符号化、方法B
- このエンコーディングはパリティを保持しません。
特許取得済みの最終的なChen-Hoエンコード
3桁の10進数のエンコード
ヘルツエンコーディング
- このエンコーディングはパリティを保持しません。
初期のChen-Ho符号化
- このエンコーディングはパリティを保持しません。
特許取得済みのChen-Hoエンコーディング
- この符号化はパリティ保存ではない。[14]
最終的なChen-Hoエンコード
- この符号化はパリティ保存ではない。[15]
ストレージ効率
参照
- 2進化10進数（BCD）
- 高密度パック 10 進数(DPD)
- 10進数基数50 / MOD40
- IBM スクオーズ
- パックされたBCD
- Unicode変換形式（UTF）（同様のエンコード方式）
- 長さ制限付きハフマン符号
注記
- ^いくつかの 4 ビット 10 進コードは 、8-4-2-1 BCD コードの代替として特に適しています。Jump -at-8 コードでは、順序付けられた状態 0 から 7 に同じ値を使用しますが、Gray BCDコードとGlixon コードでは、状態 0 から 7 の値は同じセットからのものですが、順序が異なります (ただし、Hertz、Chen–Ho、または高密度パック 10 進(DPD) エンコーディングでは、ビットが変更されずに通過するため、これは透過的です)。これらの 4 つのコードでは、最上位ビットを「大きい」値を示すフラグとして使用できます。 2 つの「大きい」値については、1 つのビットを除くすべてのビットが静的のままです (8-4-2-1 コードでは中央の 2 つのビットは常に 0、8 ジャンプ コードでは 1 つのビットがゼロですが、グレイ BCD コードでは 1 つのビットが設定され、もう 1 つのビットがクリアされます。一方、グリクソン コードでは下位の 2 つのビットは常にゼロで、1 つのビットが反転されるため、2 つの「大きい」値が透過的にスワップされます)。エンコードにはわずかな調整のみが必要です。他の 3 つのコードも、連続するビット パターンの 2 つの範囲からの値を含む 8 状態と 2 状態のグループに簡単に分割できます。 およびExcess-6 BCDおよび2 ジャンプ コードの場合、最上位ビットを使用して 2 つのグループを区別できますが、8 ジャンプ コードと比較すると、小さい値のグループには 2 つの状態のみが含まれ、大きい方のグループには 8 つの大きい値が含まれます。オブライエン タイプ Iおよびグレイ–スティビッツ コードの場合、次に重要なビットは代わりにフラグ ビットとして機能し、残りのビットは再び連続する値の 2 つのグループを形成します。したがって、これらの違いはエンコードに対して透過的なままになります。
参考文献
- ^ abc ミュラー、ジャン＝ミシェル;ブリセバーレ、ニコラス。デ・ディネシン、フィレンツェ。ジャンヌロ、クロード・ピエール。ルフェーブル、ヴァンサン。メルキオンド、ギョーム。ナタリー・レボル;ステレ、ダミアン。トーレス、セルジュ (2010)。浮動小数点演算ハンドブック (第 1 版)。ビルクホイザー。土井：10.1007/978-0-8176-4705-6。ISBN 978-0-8176-4704-9LCCN 2009939668 。
- ^ abcdefgh Hertz, Theodore M. (1971-11-02) [1969-12-15]. 「小数をコンパクトに保存するシステム」（特許）. カリフォルニア州ホイッティア、米国：North American Rockwell Corporation . 米国特許 US3618047A . 2018-07-18に取得。（8ページ）[1][2] （注：この期限切れの特許は、Chen-Ho特許でも先行技術として引用されているChen-Hoに非常によく似たコーディングシステムについて説明しています。）
- ^ 「We hear that...」Physics Today . Vol. 12, no. 2. American Institute of Physics (AIP). 1959. p. 62. doi :10.1063/1.3060696. ISSN 0031-9228. 2020年6月24日時点のオリジナルよりアーカイブ。2020年6月24日閲覧。(1ページ)
- ^ Parker, David (2003). 「名誉フェロー - 引用 - 陳天志教授」(PDF)。名誉フェロー一覧。香港中文大学(CUHK)。2014年12月25日時点のオリジナルよりアーカイブ(PDF) 。 2020年6月24日閲覧。（2ページ）
- ^ 「CHEN Tien Chi」香港中文大学（CUHK）2013年1月12日。2015年10月23日時点のオリジナルよりアーカイブ。2016年2月7日閲覧。
- ^ Wong, Andrew WF (2014-08-15) [2014-07-04, 2014-06-23, 2013-09-16, 2007-07-16, 2007-06-07, 2007-06-04, 2007-05-20, 2007-02-16]. 陳天機 Chen Tien Chi: 如夢令 Ru Meng Ling (As If Dreaming). Classical Chinese Poems in English (in Chinese and English). Translated by Hongfa (宏發), Huang (黃). Archived from the original on 2020-06-25 . Retrieved 2020-06-25 .
- ^ 「科学者に科学志向の工業団地設立の任務が与えられる」。科学速報。第11巻第2号。台北、台湾：国家科学委員会。1979年2月1日。1ページ。ISSN 1607-3509。OCLC 1658005。 2020年6月25日時点のオリジナルよりアーカイブ。 2020年6月24日閲覧。（1ページ）[3]
- ^ Tseng, Li-Ling (1988-04-01). 「ハイテクリーダーシップ：アーヴィング・T・ホー」。台湾情報。2016年2月8日時点のオリジナルよりアーカイブ。 2016年2月8日閲覧。[4]
- ^ 「台湾のシリコンバレー：新竹工業団地の発展」。フリーマン・スポグリ国際問題研究所。スタンフォード大学、スタンフォード、カリフォルニア州、米国。2000年1月11日。2020年6月26日時点のオリジナルよりアーカイブ。 2017年5月2日閲覧。
- ^ “Irving T. Ho”. San Jose Mercury News . 2003-04-26. 2020-06-25時点のオリジナルよりアーカイブ。 2020-06-25に閲覧。
- ^ Chen, Tien Chi (1971-03-12). 10進数-2進数整数変換スキーム（Irving Tze Hoへの内部メモ）。IBMサンノゼ研究所、サンノゼ、カリフォルニア州、米国：IBM。
- ^ abcdefghij Chen, Tien Chi (1971-03-29). Decimal Number Compression (PDF) (Internal memo to Irving Tze Ho). IBM San Jose Research Laboratory, San Jose, California, USA: IBM . pp. 1–4. 2012-10-17 にオリジナルからアーカイブ(PDF)されました。2016-02-07に取得。（4ページ）
- ^ IBM资深专家Frank Tung博士8月4日来我校演讲 [IBM上級専門家フランク・タン博士が8月4日に講演するために本校に来ました] (中国語と英語)。中国、広州:華南理工大学(SCUT)。 2004年8月4日。 2004 年 12 月 8 日にオリジナルからアーカイブされました。2016 年 2 月 6 日に取得。
- ^ abcdefghi Chen, Tien Chi; Ho, Irving Tze (1974-10-15) [1973-06-18]。米国カリフォルニア州サンノゼおよび米国ニューヨーク州ポキプシーで執筆。「2進化10進変換装置」（特許）。米国ニューヨーク州アーモンク：International Business Machines Corporation（IBM）。米国特許US3842414A 。2018年7月18日閲覧。（14ページ）[5][6] （注：この期限切れの特許はChen-Hoアルゴリズムに関するものです。）
- ^ abcdefghijkl Chen, Tien Chi; Ho, Irving Tze (1975 年 1 月) [1974 年 4 月]。「10 進データのストレージ効率の良い表現」。Communications of the ACM。18 ( 1)。IBM サンノゼ研究所、カリフォルニア州サンノゼ、米国および IBM システム製品部門、ニューヨーク州ポキプシー/イーストフィッシュキル、米国: Association for Computing Machinery : 49–52。doi : 10.1145/360569.360660。ISSN 0001-0782。S2CID 14301378 。（4ページ）
- ^ Chen, Tien Chi; Ho, Irving Tze (1974-06-25). 「10 進データのストレージ効率の良い表現」。研究レポート RJ 1420 (技術レポート)。IBM サンノゼ研究所、カリフォルニア州サンノゼ、米国: IBM。
- ^ abcd Cowlishaw, Michael Frederic (2014) [2000年6月]。「Chen-Ho Decimal Data encodingの概要」。IBM。2015年9月24日時点のオリジナルよりアーカイブ。2016年2月7日閲覧。
- ^ Smith, Alan Jay (1975年8月) [1975年4月]. 「TC ChenとIT Hoの論文に対するコメント」. Communications of the ACM . 18 (8). University of California , Berkeley, California, USA: 463. doi :10.1145/360933.360986. eISSN 1557-7317. ISSN 0001-0782. S2CID 20910959. CODEN CACMA2. 2020年6月3日時点のオリジナルよりアーカイブ。2020年6月3日閲覧。(1 ページ) (注: この出版物では Chen–Ho の代替法とバリエーションについても説明されています。)
- ^ Sacks-Davis, Ron (1982-11-01) [1982年1月]. 「冗長数表現の10進数演算への応用」.コンピュータジャーナル. 25 (4). コンピュータサイエンス学部、モナッシュ大学、クレイトン、ビクトリア州、オーストラリア: Wiley Heyden Ltd : 471–477. doi : 10.1093/comjnl/25.4.471 .（7ページ）
- ^ Cowlishaw, Michael Frederic (2003-02-25) [2002-05-20, 2001-01-27]。英国コベントリーで執筆。「10 進数から 2 進数へのコーダ/デコーダ」(特許)。米国ニューヨーク州アーモンク: International Business Machines Corporation (IBM)。米国特許 US6525679B1。2018年 7 月 18 日に取得。(6ページ) [7] およびCowlishaw, Michael Frederic (2007-11-07) [2004-01-14, 2002-08-14, 2001-09-24, 2001-01-27]。英国ハンプシャー州ウィンチェスターで執筆。「10進数から2進数へのコーダ/デコーダ」(特許)。米国ニューヨーク州アーモンク: International Business Machines Corporation (IBM)。欧州特許EP1231716A2。2018-07-18取得。（9ページ）[8][9][10] （注：DPDに関するこの特許では、Chen-Hoアルゴリズムについても説明されている。）
- ^ Cowlishaw, Michael Frederic ( 2002-08-07 ) [2002年5月]。「高密度パック10進エンコーディング」。IEE Proceedings - Computers and Digital Techniques。149 (3)。ロンドン、英国：電気技術者協会（IEE）：102–104。doi ： 10.1049 /ip-cdt：20020407。ISSN 1350-2387 。2017年5月20日時点のオリジナルよりアーカイブ。 2016年2月7日閲覧。（3ページ）
- ^ Cowlishaw, Michael Frederic (2007-02-13) [2000-10-03]. 「高密度パック10進数エンコーディングの概要」. IBM . 2015-09-24時点のオリジナルからアーカイブ。2016-02-07に取得。
- ^ Savard, John JG (2018) [2007]. 「Chen-Ho Encoding and Densely Packed Decimal」. quadibloc . 2018-07-03時点のオリジナルよりアーカイブ。2018-07-16に閲覧。
- ^ 7070/7074 互換機能 IBM System/370 モデル 165、165 II、および 168 (PDF) (第 2 版)。IBM 1973 年 6 月 [1970]。GA22-6958-1 (ファイル番号 5/370-13)。2018年 7 月 22 日のオリジナルからアーカイブ(PDF) 。2018 年 7 月 21 日閲覧。（31+5ページ）
さらに読む
- Bonten, Jo HM (2009-10-06) [2006-10-05]. 「Packed Decimal Encoding IEEE-754-2008」. ゲルドロップ、オランダ。2018-07-11 にオリジナルからアーカイブ。2018-07-11に取得。
- Savard, John JG (2018) [2001]. 「Base-26 Armor」. quadibloc . 2018-07-21にオリジナルからアーカイブ。 2018-07-21に取得。
- Rinaldi, Russell G.; Moore, Brian B. (1967-03-21) [1964-06-30]。米国ニューヨーク州ポキプシーおよびニューパルツで執筆。「データ圧縮/展開および圧縮データ処理」(特許)。米国ニューヨーク州: International Business Machines Corporation (IBM)。米国特許US3310786A。2018-07-18取得(60 ページ) [11]、Rinaldi, Russell G.、Moore, Brian B. (1969-05-20) [1967-01-19、1964-06-30]。米国ニューヨーク州ポキプシーおよびニューパルツで執筆。「圧縮データ形式を採用したシリアルデジタル加算器」(特許)。米国ニューヨーク州: International Business Machines Corporation (IBM)。米国特許US3445641A。2018-07-18取得(40ページ) [12] およびRinaldi, Russell G.、Moore, Brian B. (1969-03-11) [1967-01-19, 1964-06-30]。米国ニューヨーク州ポキプシーおよびニューパルツで執筆。「データ圧縮/展開および圧縮データ処理」(特許)。米国ニューヨーク州: International Business Machines Corporation (IBM)。米国特許 US3432811A。2018-07-18取得。（11ページ）[13] （注：Hertz特許とChen-Ho特許の両方で引用されている3つの期限切れの特許。）
- Bender, Richard R.; Galage, Dominick J. (1961 年 8 月)。「パッキング モード制御」。IBM技術情報開示速報4 ( 3): 61–63。
- Tilem, JY (1962 年 12 月)。「データのパッキングとアンパッキングの手段」。IBM技術情報開示速報5 ( 7): 48–49。
- Lengyel, EJ; McMahon, RF (1967 年 3 月)。「小規模メモリ向けの10進数から 2 進数への直接アドレス ジェネレーター」。IBM技術情報開示速報。9 (10): 1347。2020年 6 月 3 日閲覧。