Hi, Can anyone please give me a clear picture of squaring of a binary number in Galois field in VHDL? Many Thanks!
Squaring of a binary number in Galois field
Started by ●July 20, 2013
Reply by ●July 20, 20132013-07-20
On Sat, 20 Jul 2013 14:07:36 -0700 (PDT), lokeshpakal@gmail.com wrote:>Hi, > >Can anyone please give me a clear picture of squaring of a binary number in Galois field in VHDL? > >Many Thanks!GF2? Do you have a hardware multiplier available or not (macro, hard mult)? Eric Jacobsen Anchor Hill Communications http://www.anchorhill.com
Reply by ●July 20, 20132013-07-20
On 7/20/2013 6:23 PM, Eric Jacobsen wrote:> On Sat, 20 Jul 2013 14:07:36 -0700 (PDT), lokeshpakal@gmail.com wrote: > >> Hi, >> >> Can anyone please give me a clear picture of squaring of a binary number in Galois field in VHDL? >> >> Many Thanks! > > GF2? > > Do you have a hardware multiplier available or not (macro, hard mult)?I think this is the same guy who is discussing this in c.l.vhdl. Assume no hardware multipliers. Does that really matter? Or are you thinking the multiplier can be used as a shifter? He hasn't given much in the way of particulars. I think he is just trying to get an algorithm working in VHDL. -- Rick
Reply by ●July 20, 20132013-07-20
On Saturday, July 20, 2013 4:07:36 PM UTC-5, lokes...@gmail.com wrote:> Hi, > > > > Can anyone please give me a clear picture of squaring of a binary number in Galois field in VHDL? > > > > Many Thanks!This is pretty much an unanswerable question without specification of the irreducible polynomial used to generate the field elements, but the basic result is fairly simple to implement. For a Galois field GF(2^m), the field elements are m-bit vectors, not binary numbers as you call them, and squaring is done via an XOR net. For example, for m = 3, and the field elements being 3-bit vectors (a0, a1, a2) representing the polynomial a(z) = a0 + a1.z + a2.z^2 and the field being defined in terms of the irreducible polynomial g(z) = z^3 + z + 1, we have that [a(z)]^2 = a0 + a1.z^2 + a2.z^4 = a0 + a1.z^2 + a2.(z^2 + z) = a0 + a2.z + (a1 + a2).z^2 that is, to square (a0, a1, a2) replace it by (a0, a2, a1+a2) where that + in a1+a2 is an XOR operation. Note that we have used a couple of ideas here that might be unfamiliar to some people. First, in any GF(2^m), the "freshman's dream" is valid: (a+b)^2 = a^2 + b^2 and we used this in squaring a(z). Second, we used the notion that g(z) = z^3 + z + 1 = 0 => z^3 = z+1 to deduce that z^4 = z.z^3 = z^2 +z in the simplification. Also, for bits, y^2 = y AND y = y and so no AND gates are needed at all. The same ideas apply for larger m, but everything depends on what g(z) is since we need to know it to carry out the simplification. But in all cases, a squarer in GF(2^m) essentially has as output m bits that are obtained by XOR summations of the m input bits, including trivial single-term sums such as a1 getting replaced by a2 in the above example. Dilip Sarwate
Reply by ●July 21, 20132013-07-21
lokeshpakal@gmail.com wrote:> Can anyone please give me a clear picture of squaring of > a binary number in Galois field in VHDL?If you don't need a pipelined version, just write out the logic and let the tools optimize it. It will take more work to do the pipelined version. -- glen
Reply by ●July 21, 20132013-07-21
On Sat, 20 Jul 2013 19:01:32 -0400, rickman <gnuarm@gmail.com> wrote:>On 7/20/2013 6:23 PM, Eric Jacobsen wrote: >> On Sat, 20 Jul 2013 14:07:36 -0700 (PDT), lokeshpakal@gmail.com wrote: >> >>> Hi, >>> >>> Can anyone please give me a clear picture of squaring of a binary number in Galois field in VHDL? >>> >>> Many Thanks! >> >> GF2? >> >> Do you have a hardware multiplier available or not (macro, hard mult)? > >I think this is the same guy who is discussing this in c.l.vhdl. Assume >no hardware multipliers. Does that really matter? Or are you thinking >the multiplier can be used as a shifter? He hasn't given much in the >way of particulars. I think he is just trying to get an algorithm >working in VHDL.If it is for an FPGA with lots of unused multipliers laying around, then some logic could be saved by using the mults, even just as shifters. So that is true. Mostly, though, I just spaced out that GF multiplies don't need multipliers...I've had my head in FPGA details too much lately so multipliers were on the brain. Eric Jacobsen Anchor Hill Communications http://www.anchorhill.com
Reply by ●July 21, 20132013-07-21
On Saturday, July 20, 2013 11:55:04 PM UTC-5, Eric Jacobsen wrote:> > Mostly, though, I just spaced out that GF multiplies don't need > > multipliers...I've had my head in FPGA details too much lately so > > multipliers were on the brain. >Actually, SQUARING in a Galois field GF(2^m) does not even use AND gates, just XOR gates and re-routing of data bits across a m-bit-wide data path. For FPGA implementation, one can make a pipelined squarer (similarly, multiplier) in which all the connections are local, from cell to neighboring cell, but that takes m or 2m clock cycles to do a squaring or a multiplication. The latter use AND gates, the former do not. Dilip Sarwate
Reply by ●July 21, 20132013-07-21
On Sunday, July 21, 2013 9:07:36 AM UTC+12, lokes...@gmail.com wrote:> Hi, > > > > Can anyone please give me a clear picture of squaring of a binary number in Galois field in VHDL? > > > > Many Thanks!Did you make sure the field was square first? I find some fertilizer can help.
Reply by ●July 22, 20132013-07-22
On Sat, 20 Jul 2013 19:34:47 -0700 (PDT), dvsarwate <dvsarwate@yahoo.com> wrote:>....But in all cases, a squarer in GF(2^m) essentially >has as output m bits that are obtained by XOR summations of the >m input bits, including trivial single-term sums such as a1 getting >replaced by a2 in the above example. > >Dilip SarwateDilip is absolutely right. But let me suggest a faster method. Since a Galois Field is finite, how about a lookup table for squaring? Or, if you want to do a generic multiply, implement lookup tables that give the logarithm and exponential with respect to a primitive root. Then a multiply is simply looking up the logs of the operands, adding them modulo the order of the multiplicative group (which is one less than the size of the field) and then looking up the exponential of the result. Robert Scott Hopkins, MN
Reply by ●July 23, 20132013-07-23
On Monday, July 22, 2013 5:43:53 PM UTC-5, Robert Scott wrote:> But let me suggest a faster method. Since > > a Galois Field is finite, how about a lookup table for squaring? Or, > > if you want to do a generic multiply, implement lookup tables that > > give the logarithm and exponential with respect to a primitive root. > > Then a multiply is simply looking up the logs of the operands, adding > > them modulo the order of the multiplicative group (which is one less > > than the size of the field) and then looking up the exponential of the > > result.Robert: That is a good idea but the devil is in the details because simply looking up logs etc does not work as easily or as fast as you might think. There was a discussion about this on comp.dsp about nine years ago (which might or might not be still available on Google groups but is still there on www.dsprelated.com (Search for "+Sarwate +logarithm")) where I spelled out some useful tricks that vastly increase processing speed at the expense of only a small increase in the table size. Dilip Sarwate P.S. In case of difficulties, here is part of what I had written then. Multiplication using log tables has to deal with the awkward fact that we have no simple (finite) representation for log(0). You have set log(0) to 0 which is also log(1) .... In log-table approaches, it is helpful to use an antilog table that is twice as large as it needs to be, and to multiply "all" entries in the log table by 2. Thus, the sum of the "logarithms" of two nonzero quantities is always even, and we can look up the answer (without doing a reduction mod Q) in the double-sized antilog table. For example, in GF(2^3), the seven nonzero elements have "logs" 0, 2, 4, ... , 12 and the sums are even numbers ranging from 0 to 24. The even-numbered entries in the antilog table can be used to look up the answer. We set "log"(0) to 13 so that "log"(x) + "log"(0) is an odd number ranging from 13 to 25, while "log"(0) + "log"(0) equals 26. Thus, odd-numbered entries in the antilog table (as well as entry-26) are set to 0. With this set-up, "look up the logarithms, add, look up the antilogarithm" works without the need for modular reduction, testing both operands for 0, etc. at the expense of more memory (27 entries in the antilog table instead of 8). But note that entries numbered 1, 3, 5, 7, 9, 11 in the antilog table are not used at all, and coudld be used to store part of the log table....
