Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2002-02-08
2003-12-09
Siek, Vuthe (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000
Reexamination Certificate
active
06662346
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to finite field arithmetic circuits, and more particularly to finite field multiplication and division circuits for error correction coding and decoding.
BACKGROUND OF THE INVENTION
Reed-Solomon error-correcting codes help reduce bit error rate (BER) in applications such as data storage, digital video broadcasts, and wireless communications. Reed-Solomon codes operate on finite fields (GF(2
m
)). For high speed and low power, complex finite field arithmetic operations such as multiplication and division must be implemented efficiently.
Several different architectures that currently perform finite field arithmetic operations include standard, normal, and dual basis representations. For each representation, bit-parallel, bit-serial and digital architectures have been proposed for different application speed requirements. Most designs focus on reducing circuit area to improve speed.
Increased demand for portable DSP architectures has generated significant interest in the design of low power VLSI systems. For finite field arithmetic circuits, many approaches have been proposed for reducing power dissipation. For example, the impact of a primitive polynomial p(x) on power dissipation has been studied. The use of an XOR-tree has also been studied as a low power approach for finite field multipliers.
SUMMARY OF THE INVENTION
A method and apparatus according to the invention reduces power dissipation of a finite field arithmetic circuit having first and second circuit inputs. A first circuit transition probability of the first circuit input is calculated by applying a random input to the first circuit input and a constant input to the second circuit input. A second circuit transition probability of the second circuit input is calculated by applying a constant input to the first circuit input and a random input to the second circuit input. The first circuit transition probability is compared with the second circuit transition probability. One of the first and second circuit inputs having a lower circuit transition probability is selected.
In other features, a first time-varying rate that a first input signal to the arithmetic circuit varies is compared with a second time-varying rate that a second input signal to the arithmetic circuit varies. One of the first and second input signals having a higher time-varying rate is selected.
In yet other features, the selected one of the first and second input signals is coupled to the selected one of the first and second circuit inputs.
In other features, the circuit transition probability of the first circuit input is determined by computing node transition probabilities of circuit nodes associated with the first circuit input. The circuit transition probability of the second circuit input is determined by computing node transition probabilities of circuit nodes associated with the second circuit input.
In other features, the arithmetic circuit is a finite field multiplier. The finite field multiplier is one of a semi-systolic multiplier and a Mastrovito multiplier.
In still other features, the arithmetic circuit is a finite field multiplier implemented in a finite field divider. The finite field divider is implemented as an inverter that is connected to the finite field multiplier. The finite field multiplier is one of a semi-systolic multiplier and a Mastrovito multiplier and the inverter is implemented directly in combinatorial logic.
In still other features, the arithmetic circuit is implemented in an error correcting coding circuit. The error correction coding circuit is a Reed-Solomon error correction coding circuit.
Further areas of applicability of the present invention will become apparent from the detailed description provided hereinafter. It should be understood that the detailed description and specific examples, while indicating the preferred embodiment of the invention, are intended for purposes of illustration only and are not intended to limit the scope of the invention.
REFERENCES:
patent: 5602753 (1997-02-01), Fukui
patent: 6286022 (2001-09-01), Kaliski, Jr. et al.
patent: WO 91/20028 (1991-12-01), None
patent: WO 01/20427 (2001-03-01), None
Christof Paar “Some Remarks on Efficient Inversion in Finite Fields” Worcester Polytechnic Institute, ECE Department, Worcester, MA.
Anatha P. Chandrakasan and Robert W. Brodersen, “Minimizing Power Consumption in Digital CMOS circuits” Proceedings of the IEEE, vol. 83, No. 4, Apr. 1995.
A. G. Wassal, M. A. Hassan and M. I. Elmasry, “Low-Power Design of Finite Field Multipliers for Wireless Applications,” Department of Electrical and Computer Engineering, University of Waterloo, Waterloo, ON.
Leilei Song and, Keshab K. Parhi “Optimum Primitive Ploynomials for Low-Area Low-Power Finite Field Semi-Systolic Multipliers” IEEE, 1997 pp. 375-384.
Chris J. Nicol and Patrick Larsson, “Low Multiplier Multiplication for FIR Filters” Bell Laboratories, Lucent Technologies, Holmdel, NJ.
Surendra K. Jain, Leilei Song, “Efficient Semisystoloc Architectures for Finite-Field Arithmetic,” IEEE, 1998 pp. 101-113.
Leilei Song and Keshab K. Parhi, “Low-Energy Digit-Serial/Parallel Finite Field Multipliers,” Journal of VLSI Signal Processing 19, 1998, Kluwer Academic Publishers: Netherlands, pp. 149-166.
Feng Weishi
Yu Zhan
Levin Naum
Marvell International Ltd.
LandOfFree
Method and apparatus for reducing power dissipation in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for reducing power dissipation in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for reducing power dissipation in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3111764