Novel algorithms and VLSI design for division over GF(2m)

Chien Hsing Wu, Chien Ming Wu, Ming Der Shieh, Yin Tsung Hwang

Research output: Contribution to journal › Article

2 Citations (Scopus)

Abstract

In this paper, we present the division algorithm (DA) for the computation of b = c/a over GF(2m) in two aspects. First, we derive a new formulation for the discrete-time Wiener-Hopf equation (DTWHE) Ab = c in GF(2) over any basis. Symmetry of the matrix A is observed on some special bases and a three-step procedure is developed to solve the symmetric DTWHE. Secondly, we extend a variant of Stein's binary algorithm and propose a novel iterative division algorithm EB*. Owing to its structural simplicity, this algorithm can be mapped onto a systolic array with high speed and low area complexity.

Original languageEnglish
Pages (from-to)1129-1139
Number of pages11
JournalIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
VolumeE85-A
Issue number5
Publication statusPublished - 2002 May

Fingerprint

VLSI Design
Algorithm Design
Division
Wiener-Hopf Equations
Discrete-time
Systolic Array
Systolic arrays
Simplicity
High Speed
Binary
Symmetry
Formulation

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering
  • Applied Mathematics

Cite this

Wu, Chien Hsing ; Wu, Chien Ming ; Shieh, Ming Der ; Hwang, Yin Tsung. / Novel algorithms and VLSI design for division over GF(2m). In: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. 2002 ; Vol. E85-A, No. 5. pp. 1129-1139.
@article{e07bb021c689470a8dc690e99e35be21,
title = "Novel algorithms and VLSI design for division over GF(2m)",
abstract = "In this paper, we present the division algorithm (DA) for the computation of b = c/a over GF(2m) in two aspects. First, we derive a new formulation for the discrete-time Wiener-Hopf equation (DTWHE) Ab = c in GF(2) over any basis. Symmetry of the matrix A is observed on some special bases and a three-step procedure is developed to solve the symmetric DTWHE. Secondly, we extend a variant of Stein's binary algorithm and propose a novel iterative division algorithm EB*. Owing to its structural simplicity, this algorithm can be mapped onto a systolic array with high speed and low area complexity.",
author = "Wu, {Chien Hsing} and Wu, {Chien Ming} and Shieh, {Ming Der} and Hwang, {Yin Tsung}",
year = "2002",
month = "5",
language = "English",
volume = "E85-A",
pages = "1129--1139",
journal = "IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences",
issn = "0916-8508",
publisher = "Maruzen Co., Ltd/Maruzen Kabushikikaisha",
number = "5",

}

Wu, CH, Wu, CM, Shieh, MD & Hwang, YT 2002, 'Novel algorithms and VLSI design for division over GF(2m)', IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E85-A, no. 5, pp. 1129-1139.

Novel algorithms and VLSI design for division over GF(2m). / Wu, Chien Hsing; Wu, Chien Ming; Shieh, Ming Der; Hwang, Yin Tsung.

In: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol. E85-A, No. 5, 05.2002, p. 1129-1139.

Research output: Contribution to journal › Article

TY - JOUR

T1 - Novel algorithms and VLSI design for division over GF(2m)

AU - Wu, Chien Hsing

AU - Wu, Chien Ming

AU - Shieh, Ming Der

AU - Hwang, Yin Tsung

PY - 2002/5

Y1 - 2002/5

N2 - In this paper, we present the division algorithm (DA) for the computation of b = c/a over GF(2m) in two aspects. First, we derive a new formulation for the discrete-time Wiener-Hopf equation (DTWHE) Ab = c in GF(2) over any basis. Symmetry of the matrix A is observed on some special bases and a three-step procedure is developed to solve the symmetric DTWHE. Secondly, we extend a variant of Stein's binary algorithm and propose a novel iterative division algorithm EB*. Owing to its structural simplicity, this algorithm can be mapped onto a systolic array with high speed and low area complexity.

AB - In this paper, we present the division algorithm (DA) for the computation of b = c/a over GF(2m) in two aspects. First, we derive a new formulation for the discrete-time Wiener-Hopf equation (DTWHE) Ab = c in GF(2) over any basis. Symmetry of the matrix A is observed on some special bases and a three-step procedure is developed to solve the symmetric DTWHE. Secondly, we extend a variant of Stein's binary algorithm and propose a novel iterative division algorithm EB*. Owing to its structural simplicity, this algorithm can be mapped onto a systolic array with high speed and low area complexity.

UR - http://www.scopus.com/inward/record.url?scp=0036579483&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036579483&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:0036579483

VL - E85-A

SP - 1129

EP - 1139

JO - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

JF - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

SN - 0916-8508

IS - 5

ER -

Wu CH, Wu CM, Shieh MD, Hwang YT. Novel algorithms and VLSI design for division over GF(2m). IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. 2002 May;E85-A(5):1129-1139.

Access to Document