Hybrid multipliers

Have read this, and these are several notes:

1. Hybrid multiplier is application of bit parallel architectures to arithmetic in the subfield $GF(2^n)$ and of a bit serial structures to arithmetic in the extension field $GF((2^n)^m)$
2. The major advantage of hybrid architecture is that the number clock cycles for one multiplication is reduced by a factor of $n$. The hybrid multiplier explores thus the time-space trade-off paradigm, where the degree of the trade-off (performance versus complexity) is determined by the field decomposition $n\cdot m$
Advertisements

• mahinair2003 12:46 am on June 16, 2011 Permalink | Reply

Hi CG: I am Mahesh new to this community. I found some interesting discussions about ONB I and II multipliers. I was trying to make a 163 bit ONB multiplier. I tried to understand the paper from KOC and Sunar also the paper from M. A Hasan. but the multiplication matrix they talk about is so crazy. did u make a 163 bit NB multiplier???? Can you share the vhdl code if you have???
cheers

Standard – composite field conversion

Have just read this and this is all I understand about the paper:

1. There are various way to represent the element of $GF(2^k)$ depending on the choice of the basis or the particular construction method. If $k$ is the product of two integers as $k=m.n$, then it is possible to derive a different representation method by defining $GF(2^k)$ over the ground field $GF(2^n)$. An extension field defined over a subfield of $GF(2^k)$ other than the prime field $GF(2)$ is know as the composite field. We will use $GF((2^n)^m)$ to denote the composite field. Since there is only one field with $2^k$ elements, both the binary and the composite fields refer to this same field. However, their representation methods are different, and it is possible to obtain one representation from the other.
2. For $GF(2^8)$, $A=(a_7\alpha^7, a_6\alpha^6, ..., a1\alpha,a_0)$ where the composite field representation in $GF((2^n)^m)$ is ${\bar{A}={\bar{a}_{00},\bar{a}_{01},\bar{a}_{10},\bar{a}_{11},\bar{a}_{20},\bar{a}_{21},\bar{a}_{30},\bar{a}_{31}}}$

• Darh Templar 10:33 pm on May 28, 2010 Permalink | Reply

four posting in one day?!! pontang panting deh ngikutinnya 😀

• CG 10:46 pm on May 28, 2010 Permalink | Reply

four? coba itung lagi 😛
emang siapa suruh ngikutin?

Operations over GF(2^m): Comments and Conclusion

This book, page 231 (based on FPGA implementation) :

1. For modular multipliers, combinational circuits are too expensive in terms of area for big polynomials in cases that can’t be implemented in a single device. Sequential implementations need m (degree of f(x)) cycles to obtain a result and could be too slow. A trade-off can be obtained using a sequential circuit that computes G bits per cycle. Tables 7.5 and 7.6 show results for the 163- and 233-bits NIST-recommended polynomials.
2. Regarding squaring, combinational circuits are simpler and faster than the corresponding sequential circuits.
3. For exponentiation, the computation time depends on the number of ones in the exponent and the multiplication deter- mines the worst time. For faster exponentiation, multipli- cation such as in Sec. 7.7.5 should be used.
4. For division-inversion, the binary division can be used for in- version with good results. The MAIA inversion has the critical path in the computation of the degree of polynomials.
5. For multipliers with special irreducible polynomials (AOPs, trinomials, pentanomials), combinational circuits have the same area problems as combinational multipliers with general irreducible polynomials, but with a lower complexity (area, delay).

Simulating classic multiplication with reduction

A = 10101010
B = 10001111
P = 00011011

C = AxB mod P = 00011010

Using Perl for generating VHDL script?

Today I decide to learn Perl and run my first hello world script in Perl because I might need it for generating VHDL script as I try to simulate circuit with more bits.
Useful links:

Simulating classic multiplication

Classic multiplicationinvolves two steps: polynomial multiplication and reduction modulo an irreducible polynomial. This only tests 8 bits polynomial multiplication.

The code is a modification from here
 library ieee; use ieee.std_logic_1164.all; use ieee.std_logic_arith.all; use ieee.std_logic_unsigned.all; use work.classic_multiplier_parameters.all;

 entity classic_multiplication is port ( a, b: in std_logic_vector(M-1 downto 0); c: out std_logic_vector(M-1 downto 0); d: out std_logic_vector(2*M-2 downto 0) ); end classic_multiplication; architecture simple of classic_multiplication is component poly_multiplier port ( a, b: in std_logic_vector(M-1 downto 0); d: out std_logic_vector(2*M-2 downto 0) ); end component; -- component poly_reducer port ( -- d: in std_logic_vector(2*M-2 downto 0); -- c: out std_logic_vector(M-1 downto 0)); -- end component; -- signal d: std_logic_vector(2*M-2 downto 0); begin 

 inst_mult: poly_multiplier port map(a => a, b => b, d => d); -- inst_reduc: poly_reducer port map(d => d, c => c); end simple; 

A=10101010
B=10001111
D = A.B without reduction = 101001100000110

Next will be simulation the polynomial reduction.
Question:
Why the implementation of this book uses $x^4+x^3+x+1$ as the irreducible polynomial? Why don’t they use this list?

• waskita 7:50 pm on May 26, 2010 Permalink | Reply

Quartus? kapan nih masuk FPGA?

• CG 3:59 am on May 27, 2010 Permalink | Reply

ternyata kata promotor cukup sampe level RTL aja. tapi udah males pake modelsim, jadi pake quartus aja 🙂

wait statement error in quartus

Mentioned here that:

The Quartus® II software supports only a single VHDL wait-until statement in a process. Other VHDL wait constructs such as wait-for statements, or processes with more than one wait statement, are not synthesizable.

Useful links:

1. Table of Quartus II support for sequential statements
2. A synthesizable delay generator instead of ‘wait for statement’
3. Some discussions about this issues here and here

Now reading:

VHDL Made Easy! David Pellerin – Douglas Taylor, Prentice Hall, 1997.

Functional and Timing Simulation in VHDL

Functional Simulation:

1. Create New Project
2. Create New VHDL file, add to the project
3. Create Vector Waveform file, by selecting File> New, save the file
4. Edit> End Time, enter 200ns
5. View> Fit in Window
6. Edit> Insert Node or Bus, add names of signal (pin) to be observed or use Node Finder and set Pins: all
7. Set the input pins by highlighting the area and assign logic values
8. Assignment>Settings, click Simulator, choose Functional as the simulation mode
9. Before running the simulation, select Processing> Generate Functional Simulation Netlist
10. Run the simulation by Processing> Start Simulation

Timing Simulation:
Same as above steps, except step
8. Assignment>Settings, click Simulator, choose Timing as the simulation mode

Quartus on Mac

Have just installed Windows XP and Quartus on Mac.

I already have 3 OS and lots of compiler. Now what?

• Bobby 5:47 pm on May 10, 2010 Permalink | Reply

just play it, to get more fun. like what i do

i have 3 OS, and lots of scripter, web server, memcached, SDK’s.

• CG 9:25 am on May 11, 2010 Permalink | Reply

ok i will play and have fun later. skrg musti bisa bikin simulasi VHDL dulu biar cepet lulus sekolah 🙂

• Bobby Prabowo 12:41 pm on May 12, 2010 Permalink

manteeep deeeh yang lagi sekolah. wkwkwkwk

• CG 1:58 pm on May 12, 2010 Permalink

situ juga lagi skolah kan, ayo balapan lulus 😛

• rajv 8:16 pm on May 18, 2010 Permalink | Reply

your should teach us to install mac os as a guest os on windows-based computers….

• CG 11:14 am on May 19, 2010 Permalink | Reply

never did that 🙂 but maybe this link http://www.hackintosh.com/ would help 🙂

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel