I think that the 6502 decode ROM which matches opcode bits and sequence numbers to internal CPU functions is a very good example. It can be seen as either just a rather complex demultiplexer or, with keeping the sequencing nature in mind as a minimal, hard coded, computer program.

Does microcode have to execute like traditional software to be called microcode?

The 6502 is an interesting case. The decode ROM (PLA) gets instructions about 1/3 of the way decoded, and then there's a whole pile of random control logic [1], [2] that generates the actual control lines [3]. The output from the decode ROM consists of semi-meaningless things such as ADC/SBC in state T0, or JSR in T5 [4], and after a whole bunch of gates these get turned into the actual control functions such as S bus to A register. [3]

[1] image of the 6502 at http://www.visual6502.org/images/6502/index.html

[2] schematic http://www.visual6502.org/wiki/index.php?title=650X_Schemati...

[3] block diagram http://www.weihenstephan.org/~michaste/pagetable/6502/6502.j...

[4] details of ROM http://visual6502.org/wiki/index.php?title=6507_Decode_ROM

"Random control logic" Oxymoron?

Is the control logic really random in some way? That sounds impossible. Or at least, very highly inefficient.

No, it's obviously not random. It is carefully designed, but there is no regularity to it. The expression "random logic" is used to describe the circuitry that is "ad hoc" rather than a matrix, like RAM, registers, or an ALU.

Google the expression to learn more.

* http://www.google.co.uk/search?q=random+logic

* http://en.wikipedia.org/wiki/Random_logic

Ah, taste, one of the most important traits of a good engineer.