Bit serial aithmetic.

Bit serial aithmetic.

Post by Roger Kinke » Wed, 07 Dec 1994 06:25:05



Hi,

Could anyone recommend any good sites/references for papers giving a good
grounding in bit-serial/residual arithmetic and so forth?

Any thoughts/advice would be greatly appreciated.

Thanks for your time,

Roger

-----------------------------------------------------------------------------

   "Moorcroft", 27 Antrim Road, Lisburn,County Antrim, Northern Ireland
-----------------------------------------------------------------------------

 
 
 

Bit serial aithmetic.

Post by Edi Hiltebra » Wed, 07 Dec 1994 22:10:12


I visited Edinburgh University some years ago (19850 and I
was told that they intend to do bit serial computing with
the idea to speed up things. I'm still interested in the
results of this project. Maybe someone from Edinburgh
(Scotland) could give you some references and inform us
about the things they found out.

Greetings Edi
--
*****************************************************************************

 Electronics Laboratory                    *
 High Performance Computing                *

 
 
 

Bit serial aithmetic.

Post by Jean-Michel Mull » Thu, 08 Dec 1994 18:08:25


In article 9...@elna.ethz.ch, e...@ife.ee.ethz.ch (Edi Hiltebrand) writes:

>I visited Edinburgh University some years ago (19850 and I
>was told that they intend to do bit serial computing with
>the idea to speed up things. I'm still interested in the
>results of this project. Maybe someone from Edinburgh
>(Scotland) could give you some references and inform us
>about the things they found out.

>Greetings Edi

Maybe you wanted to talk about on-line arithmetic, which is a digit-serial
most significant digit first arithmetic that requires the use of a redundant number system. The advantage of on-line arithmetic over classical bit-serial arithmetic is 1) the ability to compute quotients, square roots, trancendental functions in serial mode, and 2) the fact that the most interesting digits are generated first. Such an arithmetic makes it possible to accelerate intrinsecally sequential calculations by allowing a digit-level pipe-line. On-line arithmetic was introduced in 1977 by Ercegovac and Trivedi. Please find below some references (I do not claim that the following list is exhaustive). Hope this helps. Jean-Michel.

@INPROCEEDINGS{BEW89,
AUTHOR = "R.H. Brackert and M.D. Ercegovac and A.N. Willson",
TITLE = "Design of an On-line Multiply-Add Module for Recursive Digital Filters.",
YEAR = "1989",
PAGES = "34-41",
EDITOR = {M. D. Ercegovac and E. Swartzlander},
BOOKTITLE = {9th Symposium on Computer Arithmetic, Santa Monica, USA},
MONTH = {sep},
PUBLISHER = {IEEE Computer Society Press}

@INPROCEEDINGS{EG83,
AUTHOR = "M.D. Ercegovac and A.L. Grnarov",
TITLE = "On-Line Multiplicative Normalization",
YEAR = "1983",
PAGES = "151-155",
BOOKTITLE = {6th Symposium on Computer Arithmetic},
PUBLISHER = {IEEE Computer Society Press} }

@ARTICLE{EL87,
AUTHOR = "M.D. Ercegovac and T. Lang",
TITLE = "On-the-fly conversion of redundant into conventional representations",
JOURNAL = "IEEE Transactions on Computers",
YEAR = "1987",
VOLUME = "C-36",
NUMBER = "7",
MONTH = Jul,
NOTE = "Reprinted in E.E. Swartzlander, Computer Arithmetic, Vol. 2, IEEE Computer Society Press Tutorial, 1990" }

@ARTICLE{EL88,
AUTHOR = "M.D. Ercegovac and T. Lang",
TITLE = "On-Line Sheme for Computing Rotation Factors",
JOURNAL = "Journal of Parallel and Distributed Computing",
YEAR = "1988",
VOLUME = "Special Issue on Parallelism in Computer Arithmetic",
NUMBER = "5",
NOTE = "Reprinted in E.E. Swartzlander, Computer Arithmetic, Vol. 2, IEEE Computer Society Press Tutorial, 1990" }

@INPROCEEDINGS{EL88a,
AUTHOR = "M.D. Ercegovac and T. lang",
TITLE = "On-line arithmetic: a design methodology and applications in digital signal processing",
YEAR = "1988",
PAGES = "252-263",
NOTE = "Reprinted in E.E. Swartzlander, Computer Arithmetic, Vol. 2, IEEE Computer Society Press Tutorial, 1990",
EDITOR = "",
BOOKTITLE = "VLSI Signal Processing III",
EDITION = "",
VOLUME = "",
NUMBER = "",
SERIES = "",
MONTH = "",
ADDRESS = "",
PUBLISHER = "",
ORGANIZATION = "",
ISBN = "" }

@ARTICLE{EL92,
AUTHOR = "M.D. Ercegovac and T. Lang",
TITLE = "On-the-fly rounding",
JOURNAL = "IEEE Transactions on Computers",
YEAR = "1992",
VOLUME = "41",
NUMBER = "12",
MONTH = Dec,
PAGES = "1497-1503" }

@ARTICLE{EO82,
AUTHOR = "V.G. Oklobdzija and M.D. Ercegovac",
TITLE = "An on-line square root algorithm",
JOURNAL = "IEEE Transactions on Computers",
YEAR = "1982",
VOLUME = "C-31",
PAGES = "70-75" }

@ARTICLE{Erc77,
AUTHOR = "M.D. Ercegovac",
TITLE = "A General Hardware-Oriented Method for Evaluation of Functions and Computations in a Digital Computer",
JOURNAL = "IEEE Trans. Comp.",
YEAR = "1977",
VOLUME = "C-26",
NUMBER = "7",
PAGES = "667-680" }

@INPROCEEDINGS{Erc78,
AUTHOR = "M.D. Ercegovac",
TITLE = "An on-line square rooting algorithm",
YEAR = "1978",
BOOKTITLE = {fourth Symposium on Computer Arithmetic},
PUBLISHER = {IEEE Computer Society Press} }

@INPROCEEDINGS{Erc84,
AUTHOR = "M.D. Ercegovac",
TITLE = "On-line Arithmetic: an Overview.",
YEAR = "1984",
PAGES = "pp 86-93",
EDITOR = "SPIE",
BOOKTITLE = {SPIE, Real Time Signal Processing VII} }

@INPROCEEDINGS{Erc91,
AUTHOR = "M.D. Ercegovac",
TITLE = "On-Line Arithmetic For Recurrence Problems",
YEAR = "1991",
BOOKTITLE = {Advanced Signal Processing Algorithms, Architectures, and implementations II},
PUBLISHER = {SPIE-The International Society for Optical Engeneering} }

@INPROCEEDINGS{ET75,
AUTHOR = "K.S. Trivedi and M.D. Ercegovac",
TITLE = "On-line algorithms for division and multiplication",
YEAR = "1975",
PAGES = "161-167",
EDITOR = "",
BOOKTITLE = "3rd Symposium on Computer Arithmetic",
EDITION = "",
VOLUME = "",
NUMBER = "",
SERIES = "",
MONTH = "",
ADDRESS = "",
PUBLISHER = "",
ORGANIZATION = "",
ISBN = "" }

@ARTICLE{ET77,
AUTHOR = "M.D. Ercegovac and K.S. Trivedi",
TITLE = "On-line algorithms for division and multiplication",
JOURNAL = "IEEE Transactions on Computers",
YEAR = "1977",
VOLUME = "C-26",
NUMBER = "7",
PAGES = "681-687",
NOTE = "Reprinted in E.E. Swartzlander, Computer Arithmetic, Vol. 2, IEEE Computer Society Press Tutorial, 1990" }

@INPROCEEDINGS{ET87,
AUTHOR = "M. D. Ercegovac and P. K. G. Tu",
TITLE = "A radix-4 on-line division algorithm.",
YEAR = "1987",
BOOKTITLE = {8th Symposium on Computer Arithmetic},
PUBLISHER = {IEEE Computer Society Press} }

@INPROCEEDINGS{ET89,
AUTHOR = "M. D. Ercegovac and P. K. G. Tu",
TITLE = "Design of On-line Division Unit.",
YEAR = "1989",
PAGES = "42-49",
EDITOR = {Milos D. Ercegovac and Earl Swartzlander},
BOOKTITLE = {proceedings of the 9th Symposium on Computer Arithmetic},
PUBLISHER = {IEEE Computer Society Press} }

@INPROCEEDINGS{ET91,
AUTHOR = "M.D. Ercegovac and P.K.G. Tu",
TITLE = "Application of on-line arithmetic algorithms to the SVD computation: preliminary results",
YEAR = "1991",
PAGES = "246-255",
EDITOR = {P. Kornerup and D. Matula},
BOOKTITLE = {proceedings of the 10th IEEE Symposium on Computer Arithmetic},
PUBLISHER = {IEEE Computer Society Press},
MONTH = {June} }

@ARTICLE{EW83,
AUTHOR = "O. Watanuki and M.D. Ercegovac",
TITLE = "Error analysis of certain floating-point on-line algorithms",
JOURNAL = "IEEE Transactions on Computers",
YEAR = "1983",
VOLUME = "C-32",
PAGES = "352-358",
NOTE = "Reprinted in E.E. Swartzlander, Computer Arithmetic, Vol. 2, IEEE Computer Society Press Tutorial, 1990" }

@INPROCEEDINGS{GHM89,
AUTHOR = "A. Guyot and Y. Herreros and J. M. Muller",
TITLE = "JANUS, an On-line Multiplier/divider for manipulating large numbers.",
YEAR = "1989",
PAGES = "106-111",
BOOKTITLE = {proceedings of the 9th Symposium on Computer Arithmetic},
PUBLISHER = {IEEE Computer Society Press} }

@INPROCEEDINGS{IO79,
AUTHOR = "M.J. Irwin and R.M. Owens",
TITLE = "On-line algorithms for the design of pipeline architectures",
YEAR = "1979",
BOOKTITLE = {4th Symposium on Computer Architecture},
PUBLISHER = {IEEE Computer Society Press} }

@ARTICLE{IO83a,
AUTHOR = "M.J. Irwin and R.M. Owens",
TITLE = "Fully Digit On-Line Networks",
JOURNAL = "IEEE Transactions on Computers",
YEAR = "1983",
NOTE = "Reprinted in E.E. Swartzlander, Computer Arithmetic, Vol. 2, IEEE Computer Society Press Tutorial, 1990" }

@ARTICLE{IO87,
AUTHOR = "M.J. Irwin and R.M. Owens",
TITLE = "Digit-pipelined arithmetic as illustrated by the paste-up system: a tutorial",
JOURNAL = "IEEE Computer",
YEAR = "1987",
PAGES = "61-73" }

@PHDTHESIS{Irw77,
AUTHOR = "M.J. Irwin",
TITLE = "An arithmetic unit for on-line computation",
YEAR = "1977",
SCHOOL = "Dept. of Computer Science, university of Illinois, Champaign-urbana, IL 61801" }

@INPROCEEDINGS{Irw78,
AUTHOR = "M.J. Irwin",
TITLE = "A pipelined processing unit for on-line division",
YEAR = "1978",
PAGES = "24-30",
EDITOR = "",
BOOKTITLE = "5th Symposium on Computer Architecture",
EDITION = "",
VOLUME = "",
NUMBER = "",
SERIES = "",
MONTH = "",
ADDRESS = "",
PUBLISHER = "IEEE Computer Society Press",
ORGANIZATION = "",
ISBN = "" }

@ARTICLE{KM88,
AUTHOR = "P. Kornerup and D.W. Matula",
TITLE = "An On-Line Arithmetic Unit for Bit-Pipelined Rational Arithmetic",
JOURNAL = "Journal of Parallel and distributed Computing",
YEAR = "1988",
VOLUME = "Special Issue on Parallelism in Computer Arithmetic",
NUMBER = "5" }

@INPROCEEDINGS{LS87,
AUTHOR = "H. Lin and H.J. Sips",
TITLE = "A novel floating-point on-line division algorithm",
YEAR = "1987",
EDITOR = "M.J. Irwin and R. Stefanelli",
BOOKTITLE = "8th IEEE Symposium on Computer Arithmetic (ARITH8)",
EDITION = "",
VOLUME = "",
NUMBER = "",
SERIES = "",
MONTH = "May",
ADDRESS = "",
PUBLISHER = "IEEE Computer Society Press",
ORGANIZATION = "",
ISBN = "" }

@INPROCEEDINGS{LS89,
AUTHOR = "H. Lin and H. J. Sips",
TITLE = "On-Line CORDIC algorithms.",
YEAR = "1989",
PAGES = "26-33",
EDITOR = {M. D. Ercegovac and E. Swartzlander},
BOOKTITLE = {proceedings of the 9th Symposium on Computer Arithmetic},
PUBLISHER = {IEEE Computer Society Press} }

@PHDTHESIS{Owe80,
AUTHOR = "R.M. Owens",
TITLE = "An arithmetic unit for on-line computation",
YEAR = "1980",
SCHOOL = "Dept. of Computer Science, The Pennsylvania State University, University Park" }

@ARTICLE{Owe83,
AUTHOR = "R.M. Owens",
TITLE = "Techniques to Reduce the Inherent Limitation of Fully Digit On-Line Arithmetic",
JOURNAL = "IEEE Transactions on Computers",
YEAR = "1983" }

@ARTICLE{BDKM93,
AUTHOR = "J.C. Bajard and J. Duprat and S. Kla and J.M. Muller",
TITLE = "Some operators for on-line radix 2 computations",
JOURNAL = "Journal of Parallel and Distributed Computing",
YEAR = "1994",
VOLUME = "22",
NUMBER = "2",
PAGES = "336-345",}

@INPROCEEDINGS{RT78,
AUTHOR = "J.G. Rusnak and K.S. Trivedi",
TITLE = "Higher radix on-line division",
YEAR = "1978",
BOOKTITLE = {fourth Symposium on Computer Arithmetic},
PUBLISHER = {IEEE Computer Society Press} }

----------------------------------------------------------------------
Jean-Michel Muller, CNRS, Lab. LIP, Ecole Normale Superieure de Lyon
46 Allee d'Italie, 69364 Lyon Cedex 07, FRANCE
Tel. +33 72 72 82 29   Fax. +33 72 72 80 80   jmmul...@lip.ens-lyon.fr

 
 
 

Bit serial aithmetic.

Post by D. J. Bernste » Thu, 15 Dec 1994 19:11:48



> On-line arithmetic was introduced in 1977 by Ercegovac and Trivedi.

Hmmm. HAKMEM 239 was in 1972, wasn't it?

---Dan

 
 
 

Bit serial aithmetic.

Post by Luiz S. Pir » Sun, 18 Dec 1994 04:06:20


Quote:>> On-line arithmetic was introduced in 1977 by Ercegovac and Trivedi.
>Hmmm. HAKMEM 239 was in 1972, wasn't it?

  Could some one point me to a source for the HACKMEM list? I have heard
 of many algoritmhs/procedures it describes but have never come across it.

  On-line would be ideal, but I will take what I can get!

  Luiz Pires.

 
 
 

1. 24-bit/16-bit divide routine for 8-bit processor

Hi All,
        I am using an NEC K/0S microcontroller to access a serial data
flash device.  Part of the spec calls for the serial data flash
interface to accept a 24-bit linear address.  In order to make this
work, I have to divide the 24-bit address by a 9-bit page size in
order to determine which page of the device to access.

        Can anyone point me to a function that might satisfy this
problem?  BTW, we are very limited on space, so it has to be done in
assembly language, and the K/0S family does not have a divide or
multiply instruction.

Thanks in advance for the help.
Guy

--

Guy Berthiaume

"With, without,
 And who'll deny,
 It's what the fighting's all about."
                          - Roger Waters

2. Bad news regarding Netgear RT328 and NAT

3. Help!! Bit serial Baugh-Wooley multiplier

4. AN: Acrobat ~DIRECT~ bitmap .BMP file generation!

5. Bit Serial Multipiler

6. LotusScript Question

7. Bit Serial Arithmetic De-mystified

8. Eliminate Secret Data Now ( 2gdqe8f)

9. Help!!!! Bit serial Baugh-Wooley multiplier

10. Bit Serial Multiply

11. : Pipelined Bit-serial multiplier with word-length delay?

12. Help: msb first bit-serial multiply reference needed

13. Bit-serial arithmetic?