JPS63225826A - 巾乗器 - Google Patents
巾乗器Info
- Publication number
- JPS63225826A JPS63225826A JP62059394A JP5939487A JPS63225826A JP S63225826 A JPS63225826 A JP S63225826A JP 62059394 A JP62059394 A JP 62059394A JP 5939487 A JP5939487 A JP 5939487A JP S63225826 A JPS63225826 A JP S63225826A
- Authority
- JP
- Japan
- Prior art keywords
- elements
- multiplier
- linear combination
- modulo
- power
- 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.)
- Granted
Links
Landscapes
- Detection And Correction Of Errors (AREA)
- Error Detection And Correction (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
産業上の利用分野
本発明は誤り訂正符号を用いる時に必要とされるガロア
拡大体の要素の２ｉ乗演算（ｉは整数）を行なう巾乗器
に関するものである。
拡大体の要素の２ｉ乗演算（ｉは整数）を行なう巾乗器
に関するものである。
従来の技術
従来の技術としては、ガロア拡大体の要素をベクトル表
現にしている場合は、乗算器を用いて２乗演算を行なっ
ている。第４図はこの従来のＸ’ ＋Ｘ＋Ｉ Ｋ！１４
かれる体ＧＦ（２’）Ｋおける乗算器を示すものであり
、１は２個のＧＦ（２）の要素の法２加算器、２は２個
のＧＦ（２）の要素の乗算器である。以上のように構成
された乗算器においては、乗算器の２人力をそれぞれ（
ａ３゜’２＋’１ｔ’Ｏ）とする時、２乗演算の結果（
ｂ３゜ｂ２．ｂ、、ｂｏ）を出力として得る。２ｉ乗演
算は乗算をし、繰り返し行なっている。
現にしている場合は、乗算器を用いて２乗演算を行なっ
ている。第４図はこの従来のＸ’ ＋Ｘ＋Ｉ Ｋ！１４
かれる体ＧＦ（２’）Ｋおける乗算器を示すものであり
、１は２個のＧＦ（２）の要素の法２加算器、２は２個
のＧＦ（２）の要素の乗算器である。以上のように構成
された乗算器においては、乗算器の２人力をそれぞれ（
ａ３゜’２＋’１ｔ’Ｏ）とする時、２乗演算の結果（
ｂ３゜ｂ２．ｂ、、ｂｏ）を出力として得る。２ｉ乗演
算は乗算をし、繰り返し行なっている。
また、ガロア拡大体の要素を指数表現にしている場合に
は、指数を２倍することにより２乗演算を行なっている
。第５図はこの従来の２乗器を示すものであシ、このよ
うに構成された従来の２乗器においては、指数表現され
た要素（’ｍ−１１’ｍ−２ｔ・・・、Ｃ０）を入力と
して上位方向に１ビツトのローテートシフトを行ない、
２乗演算された結果の指数表現（ｄｍ−＋ ＋６ｍ−２
ｉ”’ａｏ ） ＝（’ｍ−２＋ ’１ｌｌ−５＋ ”
・ｒ ’Ｏｒ ’Ｔｎ−１）が出力される。
は、指数を２倍することにより２乗演算を行なっている
。第５図はこの従来の２乗器を示すものであシ、このよ
うに構成された従来の２乗器においては、指数表現され
た要素（’ｍ−１１’ｍ−２ｔ・・・、Ｃ０）を入力と
して上位方向に１ビツトのローテートシフトを行ない、
２乗演算された結果の指数表現（ｄｍ−＋ ＋６ｍ−２
ｉ”’ａｏ ） ＝（’ｍ−２＋ ’１ｌｌ−５＋ ”
・ｒ ’Ｏｒ ’Ｔｎ−１）が出力される。
この場合、２ｉ乗演算に対しては上位方向にｉビットの
ローテートシフトを行なっている。
ローテートシフトを行なっている。
発明が解決しようとする問題点
しかしながら上記のような構成では、ベクトル表現の場
合、２乗演算に用いる乗算器の回路規模が非常に大きい
という問題点を有していた。また、通常のガロア体の要
素の処理を行なう時は２乗演算のみを必要とするのでは
なく、その他に加算や乗算が必要であるが、指数表現の
場合加算を行なうためにはリード・オンリ・メモリ上の
テーブルを用いており、全体としての回路規模は非常に
大きくなるという問題点を有していた。
合、２乗演算に用いる乗算器の回路規模が非常に大きい
という問題点を有していた。また、通常のガロア体の要
素の処理を行なう時は２乗演算のみを必要とするのでは
なく、その他に加算や乗算が必要であるが、指数表現の
場合加算を行なうためにはリード・オンリ・メモリ上の
テーブルを用いており、全体としての回路規模は非常に
大きくなるという問題点を有していた。
本発明はかかる点に鑑み、回路規模の小さい巾乗器を提
供することを目的とする。
供することを目的とする。
問題点を解決するための手段
本発明は、ベクトル表現されたＧＦ（２！ｌ＋）の要素
の２ｉ乗演算を（、Ｆ（２）上のｍ ）＜、 ｍ行列の
線形結合演算として行なう線形結合演算手段を備えた巾
乗器である。
の２ｉ乗演算を（、Ｆ（２）上のｍ ）＜、 ｍ行列の
線形結合演算として行なう線形結合演算手段を備えた巾
乗器である。
作用
本発明は前記線形結合演算手段の回路規模が非常に小さ
いことにより、ベクトル表現されたＧＦ（２ジの要素に
対して従来利用していた乗算器と比べて回路規模の小さ
い巾乗器を構成する。
いことにより、ベクトル表現されたＧＦ（２ジの要素に
対して従来利用していた乗算器と比べて回路規模の小さ
い巾乗器を構成する。
実施例
第１図は本発明の第１の実施例におけるｘ４＋ｘ＋１に
よって導かれる体ＧＦ（２）上に２乗器の構成を示すも
のである。第１図において、３はＧＦ（２）の要素の法
２加算器である。以上のように構成された本実施例の２
乗器について、以下その動作を説明する。入力人＝（２
Ｌ３ ＋ ’ ２＋ ’ 、＋ ？ＬＯ）に対し、出力
Ｂ＝（ｂ３．ｂ２．ｂｌ、ｂ。）−人２を求める演算は
、用いた体ＧＦ（２’）の原始元をα＝（Ｏｏｌｏ）と
すると Ｂ＝ａ −Ａｄ３＋ａ２・Ａ（！２＋ＩＬ、−Ａ（！
＋ａｏ−１＝（ａ、、ａ、＋ａ３，２Ｌ、、、ａｏ＋ａ
、、）但し、Ａα”（２Ｌｏ”３＋’２”３＋’＋”２
＋２Ｌ１）Ａα””（’＋ Ｉ’Ｏ”３１”２＋２
Ｌ５１’２）ムα”（’２ ＋Ｊ ｒ＆ｏ”ｓ
ｚ”３）であることによシ のように線形結合演算に変換できる。ここで、十で表さ
れる演算は法２加算である。第１図の回路はこの線形結
合演算を行なう。以上のように本実施例によれば、線形
結合演算を行なうことにより、第４図に示す従来例では
１５個のＧＦ（２）上の法２加算器と１６個のＧＦ（２
）上の乗算器により構成されていた回路を２個の法２加
算器で構成することができる。
よって導かれる体ＧＦ（２）上に２乗器の構成を示すも
のである。第１図において、３はＧＦ（２）の要素の法
２加算器である。以上のように構成された本実施例の２
乗器について、以下その動作を説明する。入力人＝（２
Ｌ３ ＋ ’ ２＋ ’ 、＋ ？ＬＯ）に対し、出力
Ｂ＝（ｂ３．ｂ２．ｂｌ、ｂ。）−人２を求める演算は
、用いた体ＧＦ（２’）の原始元をα＝（Ｏｏｌｏ）と
すると Ｂ＝ａ −Ａｄ３＋ａ２・Ａ（！２＋ＩＬ、−Ａ（！
＋ａｏ−１＝（ａ、、ａ、＋ａ３，２Ｌ、、、ａｏ＋ａ
、、）但し、Ａα”（２Ｌｏ”３＋’２”３＋’＋”２
＋２Ｌ１）Ａα””（’＋ Ｉ’Ｏ”３１”２＋２
Ｌ５１’２）ムα”（’２ ＋Ｊ ｒ＆ｏ”ｓ
ｚ”３）であることによシ のように線形結合演算に変換できる。ここで、十で表さ
れる演算は法２加算である。第１図の回路はこの線形結
合演算を行なう。以上のように本実施例によれば、線形
結合演算を行なうことにより、第４図に示す従来例では
１５個のＧＦ（２）上の法２加算器と１６個のＧＦ（２
）上の乗算器により構成されていた回路を２個の法２加
算器で構成することができる。
第２図は本発明の第２の実施例におけるｘ ８ ＋Ｘ
＋Ｘ ＋Ｘ ＋１によって導かれる体ＧＦ（２８
）上の２３乗器の構成を示すものである。第２図におい
て４はＧＦ（２）の要素の法２加算器である。前記のよ
うに構成された第２の実施例の２３乗器について以下そ
の動作を説明する。入力Ａ＝（’ ７ ＋ ’ ｆ、
＋ ’ ５ ＋ ’ ４ ＋ ａ３ ＋ ’ ２＋ ａ
ｌｒ ’ Ｑ ）に対し１出力Ｂ＝（ｂ７．ｂ６．ｂ５
．ｂ４．ｂ３．ｂ２．ｂｌ、ｂｏ）＝Ａ２は、Ｃ” （
’ ７ ｒ ’ ６ｒ ’ ５ ｒ ’ ４ 、ｃ３
ｒ ｃ２ｉ ｃＩ ｌ ｃＤ ）２人 とおくと であることより という線形結合演算により得られる。第２図の回路はこ
の線形結合演算を行なう。以上のように本実施例によれ
ば、線形結合演算を行なうことにより、従来３個のＧＦ
（２８）上の乗算器を必要とした２３乗演算回路を１３
個のＧＦ（２）上の法２加算器により構成することがで
きる。
＋Ｘ ＋Ｘ ＋１によって導かれる体ＧＦ（２８
）上の２３乗器の構成を示すものである。第２図におい
て４はＧＦ（２）の要素の法２加算器である。前記のよ
うに構成された第２の実施例の２３乗器について以下そ
の動作を説明する。入力Ａ＝（’ ７ ＋ ’ ｆ、
＋ ’ ５ ＋ ’ ４ ＋ ａ３ ＋ ’ ２＋ ａ
ｌｒ ’ Ｑ ）に対し１出力Ｂ＝（ｂ７．ｂ６．ｂ５
．ｂ４．ｂ３．ｂ２．ｂｌ、ｂｏ）＝Ａ２は、Ｃ” （
’ ７ ｒ ’ ６ｒ ’ ５ ｒ ’ ４ 、ｃ３
ｒ ｃ２ｉ ｃＩ ｌ ｃＤ ）２人 とおくと であることより という線形結合演算により得られる。第２図の回路はこ
の線形結合演算を行なう。以上のように本実施例によれ
ば、線形結合演算を行なうことにより、従来３個のＧＦ
（２８）上の乗算器を必要とした２３乗演算回路を１３
個のＧＦ（２）上の法２加算器により構成することがで
きる。
第３図は本発明の第３の実施例におけるＸ＋ｘ４＋ｘ３
＋ｘ２＋１によって導かれ、１４Ｆ Ｃ２８）上の２−
１乗器の構成を示すものである。第３図において５はＧ
Ｆ（２）の要素の法２加算器である。
＋ｘ２＋１によって導かれ、１４Ｆ Ｃ２８）上の２−
１乗器の構成を示すものである。第３図において５はＧ
Ｆ（２）の要素の法２加算器である。
前記のように構成された第２の実施例の２ 乗器につい
て以下その動作を説明する。入カム＝（ａ、、ａ６．ａ
５．ａ、、ａ、、ａ、、、ａ、、ａｏ）に対し、出力Ｒ
＝ （ｂ、、ｂ６．ｂ５．ｂ４．ｂ、、ｂ、、、ｂ、、
ｂｏ）＝人２−′は、 という線形結合演算により得られる。第３図の回路はこ
の線形結合演算を行なう。以上のように本実施例によれ
ば、線形結合演算を行なうことにより、従来ではベクト
ル表現された要素についてはリード・オンリ・メモリを
用いて求めていた２−１乗演算を１０個のＧＦ（２）上
の法２加算器により求めることができる。
て以下その動作を説明する。入カム＝（ａ、、ａ６．ａ
５．ａ、、ａ、、ａ、、、ａ、、ａｏ）に対し、出力Ｒ
＝ （ｂ、、ｂ６．ｂ５．ｂ４．ｂ、、ｂ、、、ｂ、、
ｂｏ）＝人２−′は、 という線形結合演算により得られる。第３図の回路はこ
の線形結合演算を行なう。以上のように本実施例によれ
ば、線形結合演算を行なうことにより、従来ではベクト
ル表現された要素についてはリード・オンリ・メモリを
用いて求めていた２−１乗演算を１０個のＧＦ（２）上
の法２加算器により求めることができる。
なお、ＧＦ（ｐ）における９１乗演算（ｉは整数）も線
形結合演算に変換して回路規模の小さい巾乗器を構成す
ることは可能である。
形結合演算に変換して回路規模の小さい巾乗器を構成す
ることは可能である。
発明の詳細
な説明したように、本発明によれば、
ＧＦ（２）の要素に対し回路規模の非常に小さい巾乗器
を構成することができ、その実用的効果は大きい。
を構成することができ、その実用的効果は大きい。
第１図は本発明における第１の実施例の２乗器の信号線
図、第２図は本発明の第２の実施例の２３乗器の信号線
図、第３図は本発明の第３の実施例の２−１乗器の信号
線図、第４図は従来の２乗器として用いられる乗算器の
信号線図、第５図は従来の２乗器の信号線図である。 １．３，４．５・・・・・・ＧＦ（２）の要素の法２加
算器、２・・・・・・ＧＦ（２）の要素の乗算器。 代理人の氏名 弁理士 中 尾 敏 男 ほか１名第１
図 第３図 第５図
図、第２図は本発明の第２の実施例の２３乗器の信号線
図、第３図は本発明の第３の実施例の２−１乗器の信号
線図、第４図は従来の２乗器として用いられる乗算器の
信号線図、第５図は従来の２乗器の信号線図である。 １．３，４．５・・・・・・ＧＦ（２）の要素の法２加
算器、２・・・・・・ＧＦ（２）の要素の乗算器。 代理人の氏名 弁理士 中 尾 敏 男 ほか１名第１
図 第３図 第５図
Claims (2)
- （１）ガロア体ＧＦ（２）の拡大体ＧＦ（２＾ｍ）の要
素の２＾ｉ乗演算（ｉは整数）を、要素のベクトル表現
に対するＧＦ（２）上におけるｍ×ｍ行列による線形結
合演算として行なう線形結合演算手段を備えたことを特
徴とする巾乗器。 - （２）線形結合演算手段が法２加算器のみを用いて構成
されていることを特徴とする特許請求の範囲第１項記載
の巾乗器。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP62059394A JP2845428B2 (ja) | 1987-03-13 | 1987-03-13 | 巾乗器 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP62059394A JP2845428B2 (ja) | 1987-03-13 | 1987-03-13 | 巾乗器 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS63225826A true JPS63225826A (ja) | 1988-09-20 |
| JP2845428B2 JP2845428B2 (ja) | 1999-01-13 |
Family
ID=13112025
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP62059394A Expired - Lifetime JP2845428B2 (ja) | 1987-03-13 | 1987-03-13 | 巾乗器 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP2845428B2 (ja) |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS58133062A (ja) * | 1982-02-02 | 1983-08-08 | Nec Corp | バイトシリアルエンコ−ダ |
| JPS58219649A (ja) * | 1982-06-15 | 1983-12-21 | Toshiba Corp | ガロア体における除算装置 |
-
1987
- 1987-03-13 JP JP62059394A patent/JP2845428B2/ja not_active Expired - Lifetime
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS58133062A (ja) * | 1982-02-02 | 1983-08-08 | Nec Corp | バイトシリアルエンコ−ダ |
| JPS58219649A (ja) * | 1982-06-15 | 1983-12-21 | Toshiba Corp | ガロア体における除算装置 |
Also Published As
| Publication number | Publication date |
|---|---|
| JP2845428B2 (ja) | 1999-01-13 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN117032801A (zh) | 可用于sha256的指令执行方法、设备、数据处理系统及芯片 | |
| CN100422926C (zh) | 多项式算术运算 | |
| JPS63225826A (ja) | 巾乗器 | |
| WO1994015406A1 (fr) | Procede et circuit de correction d'erreurs | |
| JPS6024650A (ja) | ガロア体上の演算回路 | |
| JP2701378B2 (ja) | 演算方式 | |
| JP3210420B2 (ja) | 整数上の乗算回路 | |
| JPS6269728A (ja) | 誤り訂正回路 | |
| JP2550597B2 (ja) | ２乗器 | |
| JPS6324723A (ja) | 有限体上の演算装置 | |
| Murakami et al. | Multichannel convolutional coding systems over a direct sum of Galois fields | |
| JP2595820B2 (ja) | ガロア拡大体演算器 | |
| JPS6136653B2 (ja) | ||
| SU1672438A1 (ru) | Устройство дл умножени двух элементов конечного пол GF(2 @ ) | |
| Truong et al. | Efficient multiplication algorithm over the finite fields GF (qm) where q= 3, 5 | |
| JP3186612B2 (ja) | 乗算器 | |
| TW406480B (en) | Encoding and decoding apparatus | |
| JPH0477120A (ja) | 可変長符号化装置 | |
| JPS5850463B2 (ja) | 誤り訂正符号化および復号化システム | |
| SU1524045A1 (ru) | Четырехвходовый одноразр дный сумматор | |
| JPS62253228A (ja) | パリテイあるいはシンドロ−ム生成回路 | |
| SU566375A2 (ru) | Устройство дл исправлени одиночных и обнаружени многократных ошибок | |
| JPH04182756A (ja) | データ入出力装置 | |
| JPS62150938A (ja) | 有限体の乗算回路 | |
| Ksir et al. | Reliability bounds and direct computation of the reliability of a consecutive k-out-of-n: F system with Markov dependence |