Sort of Gray code to binary converter

[Fred Bloggs]

I say 'sort of' because the input I have is not true reflected binary

Gray code. The input is a wind direction sensor with eight discrete
positions. They are activated by a small magnet which triggers either
one or two sensors at any time. Thus the eight sensors produce the
following sequence:

00000001
00000011
00000010
00000110
00000100
00001100
00001000
00011000
00010000
00110000
00100000
01100000
01000000
11000000
10000000
10000001

What logic do I need to convert these 16 values to a 4-bit binary
number.

Thanks for your attention.

The direct approaches are uninteresting- like the dumb C stuff that
presumably uses 16 I/O which seems burdensome on the embedded flea power
hardware. The answer in terms of an efficient solution is not only pat
but also obvious if you can recognize the analogy with another
well-known method...

 

[Andrew Holme]

I say 'sort of' because the input I have is not true reflected binary
Gray code. The input is a wind direction sensor with eight discrete
positions. They are activated by a small magnet which triggers either
one or two sensors at any time. Thus the eight sensors produce the
following sequence:

00000001
00000011
00000010
00000110
00000100
00001100
00001000
00011000
00010000
00110000
00100000
01100000
01000000
11000000
10000000
10000001

What logic do I need to convert these 16 values to a 4-bit binary
number.

Thanks for your attention.

16V8 PAL

Inputs = ABCDEFGH

0xxxxxx1 = 0 or 1
xxxxxx10 = 2 or 3
xxxxx10x = 4 or 5
xxxx10xx = 6 or 7
xxx10xxx = 8 or 9
xx10xxxx = 10 or 11
x10xxxxx = 12 or 13
10xxxxxx = 14 or 15

Output0 = AB + BC + CD + DE + EF + FG + GH + AH
Output1 = A&/B + C&/D + E&/F + G&/H
Output2 = A&/B + B&/C + E&/F + F&/G
Output3 = A&/B + B&/C + C&/D + D&/E

 

[Frank Bemelman]

Probably/possibly it is in this situation, but there are other things
a compiler can do with a switch/case construct than a simple series of
comparisons (linear search). Binary tree, table, hash, etc.

Right. If a large enough switch statement where an 8 bit switch argument
is used, a binary tree comes to mind, but with smaller switches it all
boils down to series of if/else cases. Writing it in if/else form, it
allows you to optimize for the situation at hand, put the most likely
possibilities at the top, things like that. This is all very understandable,
as there exists no assembly equivalent for a switch statement, so any
cleverness, if any, has to come from the compiler if you depend on the
switch statement. I have yet to see a compiler that uses anything else
than if/else approach, but perhaps I haven't used large enough switches
to see a different behaviour.

 

[Fred Bloggs]

This is all very understandable,
as there exists no assembly equivalent for a switch statement, so ...

Whatever happened to doing an indirect jump through a table ( of
addresses) indexed into by the argument?

 

[John Larkin]

Whatever happened to doing an indirect jump through a table ( of
addresses) indexed into by the argument?

Exactly. A 256-entry lookup table, indexed by the eight input bits,
delivers a 4-bit code for every input combination. Fast. That sure
beats a bushel of logic.

I did a *very* fast 16-bit sine function a while back. It was 128
kbytes long.

There's nothing you can't do in assembly. If a compiler can generate
machine code, I can too.

John

 

[Fred Bloggs]

Exactly. A 256-entry lookup table, indexed by the eight input bits,
delivers a 4-bit code for every input combination. Fast. That sure
beats a bushel of logic.

I did a *very* fast 16-bit sine function a while back. It was 128
kbytes long.

There's nothing you can't do in assembly. If a compiler can generate
machine code, I can too.

John

Don't these "Small C" compilers allow them to mix assembly with high
level? Seems dumb if they don't.

 

[Robert Scott]

Using 74LS00 series logic I can do it with the following chips:

74LS00 x 4
74LS20 x 2
74LS30 x 1
74LS04 x 1






-Robert Scott
Ypsilanti, Michigan

 

[Spehro Pefhany]

Exactly. A 256-entry lookup table, indexed by the eight input bits,
delivers a 4-bit code for every input combination. Fast. That sure
beats a bushel of logic.

Something like this?

const unsigned char wlut[256] = {0xFF,0x00,0x02,0x01,0x04,0xFF,
0x03,0xFF,0x06,0xFF,0xFF,0xFF,0x05,0xFF,0xFF,0xFF,0x08,0xFF,0xFF,
0xFF,0xFF,0xFF,0xFF,0xFF,0x07,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
0x0A,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
0xFF,0xFF,0xFF,0x09,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0x0C,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0x0B,
0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
0xFF,0xFF,0xFF,0xFF,0xFF,0x0E,0x0F,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
0xFF,0xFF,0xFF,0xFF,0x0D,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
0xFF,0xFF,0xFF};

direction = wlut[input];

How fast is that wind direction going to change? ;-) The table can
consume 448 bytes in a typical midrange PIC, which may not be
insignificant, and table lookup is pretty ugly as well (none of your
dedicated CPU32 table instructions.. and paging has to be handled).

I did a *very* fast 16-bit sine function a while back. It was 128
kbytes long.

There's nothing you can't do in assembly. If a compiler can generate
machine code, I can too.

John

Frank's point is that there is no exact equivalent, so the compiler at
least has a chance to do it better than the most obvious way- for
example by presorting the cases and doing a tree. But I agree with
him, most compilers on most platforms will generate a series of
comparisons for a small switch/case construct.


Best regards,
Spehro Pefhany

 

[Frank Bemelman]

Whatever happened to doing an indirect jump through a table ( of
addresses) indexed into by the argument?

That's nice if you have some control over the argument, like being
restricted to 8 bit etc. In this case, only 16 different argument values
exist. You can sacrifice a table of 256 vectors to gain some speed,
if you must, and if you have the room for it.

 

[Frank Bemelman]

How fast is that wind direction going to change? ;-) The table can
consume 448 bytes in a typical midrange PIC, which may not be
insignificant, and table lookup is pretty ugly as well (none of your
dedicated CPU32 table instructions.. and paging has to be handled).

Ugliness is in the eye of the beholder. The CPU couldn't care less

[snip]

 

[Spehro Pefhany]

Ugliness is in the eye of the beholder. The CPU couldn't care less

Any ugly CPU like a PIC probably looks forward having its PCLATH
diddled once in a while.


Best regards,
Spehro Pefhany

 

[Ken Smith]

Using 74LS00 series logic I can do it with the following chips:

74LS00 x 4
74LS20 x 2
74LS30 x 1
74LS04 x 1

I've got you very beat on chip count but mine are higher level chips.
See my post elsewhere in this thread.

Since this doesn't have to be fast, you could use open collector/drain
gates to wire-or things. 8 chips seems like way too many for this job.

A SIP R-pack and a comparitor could do the LSB if the high levels are well
known.

 

[[email protected]]

In C it is simple. Don't do clever tricks, you'll only forget why they
worked later on. Do it the obvious way:

char code2number(unsigned char code)
{
switch (code) {

or

Y = Table[X];

I considered that one. That requires an array of 256 elements 93.75% or
which simply store errors/illegal values. The switch statement on the
other hand requires less typing (16 cases instead of 256 values).

 

[Robert Scott]

I've got you very beat on chip count but mine are higher level chips.
See my post elsewhere in this thread.

How about comparing solutions on the basis of equivalent number of
gates? Obviously an ASIC could be built to do this job, but the
puzzle, as an intellectual exercise, is more interesting if you place
complexity limitations on the solution.

(For a practical solution I would just program a PIC.)

-Robert Scott
Ypsilanti, Michigan

 

[John Larkin]

How about comparing solutions on the basis of equivalent number of
gates? Obviously an ASIC could be built to do this job, but the
puzzle, as an intellectual exercise, is more interesting if you place
complexity limitations on the solution.

(For a practical solution I would just program a PIC.)

Or even easier, a 22CV10.

John

 

[Mac]

Exactly. A 256-entry lookup table, indexed by the eight input bits,
delivers a 4-bit code for every input combination. Fast. That sure
beats a bushel of logic.

I did a *very* fast 16-bit sine function a while back. It was 128
kbytes long.

Ah, a straight LUT. That is how the AD DDS's do it, too.

There's nothing you can't do in assembly. If a compiler can generate
machine code, I can too.

John

Assembly isn't very portable, though. Sometimes that matters, and
sometimes it doesn't.

Sounds like for you it usually doesn't. ;-)

--Mac

 

[John B]

Well so far we've got quite a plethora of answers. Ken seems to be
ahead of the field in the hardware stakes, although he's keeping the
design under wraps just now ;-). I like the 16V8 or 22V10 PLD approach
and that could yet creep to the front of the field.

The software field is more open. Several people had suggested a PIC,
that's definitely not in the field as the hardware is tooo.. ugly! Now
an AVR, yes that's a goer, but not in assembler as that is ugly as
well. So we're probably looking at 'C' on an AVR as the front runner.
Look-up tables are too wasteful and if(); else if() or switch{}
contructs are too ugly so let's have some lateral thinking.

It's interesting to see that Win is keeping his powder dry. As one of
the perpetrators of my long time reference book of 20 odd years
standing I would like to know what he's thinking.

Anyway there's still nine days left until the Northern Hemisphere
Winter Solstice (that's for the pedants) and, as long as we can keep
the momentum up, the competition closes three days after that.

It looks as though there will have to be two toasts drunk as a
celebration. I'll need to get out my zimmer frame to be able to stand
up after that.

Happy thinking.

 

[Ken Smith]

Y = Table[X];

I considered that one. That requires an array of 256 elements 93.75% or
which simply store errors/illegal values. The switch statement on the
other hand requires less typing (16 cases instead of 256 values).[/QUOTE]

In ASM you can do like this:

Table:
rept 256 ; Repeat 256 times
db 0FFH ; Fill with error
endm ; End repeat

org Table+00000011 ; Address the cell
db 1 ; Put the value in
org Table+00000110
db 2
..... etc .......
org Table + 256 ; put the pointer to after the table
.... more code ...

As is often the case, it is easier to do in ASM.

 

[Ken Smith]

[...]

I've got you very beat on chip count but mine are higher level chips.
See my post elsewhere in this thread.

How about comparing solutions on the basis of equivalent number of
gates? Obviously an ASIC could be built to do this job, but the
puzzle, as an intellectual exercise, is more interesting if you place
complexity limitations on the solution.

(For a practical solution I would just program a PIC.)

A PIC has a really huge number of gates inside. Personally, I'd more
likely put it into a CMOS 22V10. Both you and my practical solutions
contain more logic than the ones we are comparing.

A real contest would be to do it in terms of transistors.

 

[Ken Smith]

Or even easier, a 22CV10.

Yes.
Get one of the "zero power" ones and you can run it for a couple of years
on a 9V battery.