The Short Circuit

Mike Morgan's technical journal

My son is learning how to solve 4x4 and 5x5 cubes, and he noticed some errors in Dan Harris' book, "Speedsolving the Cube:  Easy-to-Follow, Step-by-Step Instructions for Many Popular 3-D puzzles."

The book has an errata, but the website where the errata was published is down and has been for some time.  So I am going to republish it here, for the benefit of others who may have the book and no list of errors.
Continue Reading »

Electrical engineering rules of thumb (EEROTs) are time saving design guidelines used by electrical engineers.  However, not all EEROTs are created equal, and many are not timeless.   I have witnessed engineers, including myself, blindly apply EEROTs, only to regret it the morning after. 

This raises the question:  how does a young electrical engineer know when to use an especially alluring rule of thumb?  The answer is:  one must keep in mind not only the EEROT, but also its rationale.

Here, we begin what will hopefully be the first in a series of posts discussing various EEROTs.

Old EEROT #1: Do not use signal initializations in synthesizable code

Signal initilization in synthesizable VHDL to initialize registers used to be a cardinal sin because initialization was simulatable but not sythesizable.  What this means is it would behave one way in simulation, but infer logic that did not behave the same way in practice.  This led to behavioral discrepancies between simulation and hardware.  Consequently, a popular EEROT used to be "do not use signal initialization in synthesizable code." 

For example, Ben Cohen, in VHDL coding styles and methodologies, wrote "initialization is ignored by sythesizers".(Cohen 1999, p. 119)  To be fair, Mr. Cohen's advice is still correct when targeting ASICs, and it was probably valid for FPGAs back in 1999, but FPGA synthesizers have evolved since then, and no longer universally ignore initializations when initialized signals infer registers.

Specifically, in addition to the connections among registers and the specification of combinatorial logic, FPGAs, unlike most if not all ASICs, have an innate capacity to provision the values registers contain immediately after configuration, independent of reset.

In response, FPGA synthesizers initially provided out-of-band mechanisms to specify the after-configuration value of registers.  One such mechanism took advantage of VHDL's ability to specify user defined attributes.  In the following (now depreciated) example, based on XST, a VHDL user defined attribute init is applied to my_reg, in order to control its value upon exiting FPGA configuration:

Continue Reading »

James Clerk Maxwell

James Clerk Maxwell

In a segment on James Clerk Maxwell, the Nature podcast narrator begins at 22:29:

A hundred and fifty years ago this month, a 30 year old Scotsman called James Clerk Maxwell wrote down the four equations that made him famous.(Nature 2011)

One problem with Nature's introduction is Maxwell's equations did not make him famous, initially.  Another is he did not write down four equations; he wrote down twenty.  It was Oliver Heaviside who simplified Maxwell's equations to the four equations we know and love (or loathe) today, as is documented in two biographies by Basil Mahon: one on James Clerk Maxwell, and the other on Oliver Heaviside.(Mahoon 2004, 2009) Wikipedia also has this documented if you do not have access to the books.
Continue Reading »

Just some hack code I threw together for evalating the Josephus Problem.

The Josephus problem described in Concrete Mathematics can be stated in an equivalent yet family friendly form as follows: n players stand in a circle to play a game of “Josephus tag”. When the game starts, the first player tags the second player, and then the third person tags the fourth, and so on and so forth. When a player is tagged, he is out. After the first round, subsequent rounds ensue until the last survivor, who declares herself the winner.

For a game with n players, which position should one select to ensure survival and hence victory?

This program will spew the order of the players who are out in reverse order, allowing you to analyze the results in an effort to find patterns for the last survivor, the second to the last survivor, and so on. For exmaple, here are the rusults for the Josephus problem with 2 through 9 players. Looking at the n=9 case, player 3 is the winner, while player 7 was the last to be tagged.

Reverse Order Out    2:     1    2
Reverse Order Out    3:     3    1    2
Reverse Order Out    4:     1    3    4    2
Reverse Order Out    5:     3    5    1    4    2
Reverse Order Out    6:     5    1    3    6    4    2
Reverse Order Out    7:     7    3    5    1    6    4    2
Reverse Order Out    8:     1    5    7    3    8    6    4    2
Reverse Order Out    9:     3    7    9    5    1    8    6    4    2

Source code is below the fold. As always, for legal reasons, it is provided as is.

Continue Reading »

My 9 year old son Alexander came up with a couple of closed form solutions to the Joesphus problem.  Really.  If this helps you, please leave a comment, he will enjoy it.

 A discussion of his solution (conjectures) and an attempted proof by me of one of them can be found as the first link in the references.

His main conjecture is:

    J(n)=2(n-2^{\lfloor\log_2 n \rfloor})+1, \mbox{ for } {n} \ge {1}

where

    floor(x)=\lfloor{x}\rfloor

is the largest integer not greater than x.
Continue Reading »

 

The circuit in figure 1 is useful for passing pulses across ascynchronous clock domains. Its purpose is to convert a pulse in one clock domain to another clock domain, while mitigating metastability inherant in clock domains crossing (CDC).(1) VHDL source code can be found below

For our purposes, a pulse is defined as a synchronous signal one clock period in duration. Pulses may be used to load registers, or to indicate status such as "output valid", as two examples. When passing busses from one clock domain to another, resynchronized pulses may be utilized to ensure that all bits in a data bus are stable in the destination domain before being used as valid data. 

Figure 1: Circuit for passing pulse across clock domains

Figure 1: Circuit for passing pulse across clock domains

Theory of circuit

A pulse is converted to state change with a T flip flop, TFF0. The state change is synchronized to the destination clock domain via two cascaded D flip flops (DFFs), DFF0 and DFF1. The output of DFF1 is cascaded to DFF2, where the input and output of DFF2 are exclusived ORed to create a pulse in the destination clock domain. 

Detailed explanation of circuit 

Continue Reading »

Quoted in EDN

Old news, but I was quoted by Ron Wilson for an article in EDN. The topic was power estimation for FPGAs. Before the interview, I made a deal with my boss that if Mr. Wilson quoted me in his article, I'd get an office with a door.

It was flattering to be quoted, but I didn't get the office.
Links

Bruce Schneier’s Blowfish was mentioned again on 24. This time, a character on 24 claimed that the designer of the algorithm put in a backdoor.

Blowfish is neat little encryption algorithm designed in the mid 1990s by Bruce Schneier. I first came across it in the April 1994 issue of Dr. Dobb's Journal, a magazine for working computer programmers and hobbyists.

The magazine ran an associated contest to crack blowfish, and I naively took the bait. The deadline passed without success.  But soon thereafter, I discovered a problem with the C-source code implementation: a sign extension bug.

Specifically, a key in blowfish was represented as array of char in the early C-source implementations.  A char is a type in the C language.   The C language doesn't specify whether chars are supposed to be treated as  signed or unsigned.  However, many compilers treat chars as signed by default,  unless the programmer explicitly declares or casts the char as unsigned.

Continue Reading »

© 2016 The Short Circuit | Entries (RSS) and Comments (RSS) |