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

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
  • Applied Mathematics
  • Electrical and Electronic Engineering

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 Ming-Der Shieh and Hwang, {Yin Tsung}",
year = "2002",
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, M-D & 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, 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

Y1 - 2002

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

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 M-D, Hwang YT. Novel algorithms and VLSI design for division over GF(2m). IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. 2002;E85-A(5):1129-1139.

Access to Document