I know garth has an article on this in his 6502 primer, however to help me I would like to learn the actual mechanics/mathematics of address decoding. I suppose it wont be to different for related processors like the 8085 and 6800

_________________
JMP $FFD2

No, it would all be the same. This is basic boolean logic, well actually boolean algebra.

The basic question is, given a 16-Bit address, which chip gets turned on for each individual address.

Let's take a contrived case of a 4K RAM chip, assuming something existed.

To get 64K of RAM, you need 16 chips, right? 16 x 4 = 64.

Now, each chip itself would need 12 bits for addressing, since 2^12 is 4096 (4K).

So, each chip, in this case, will have 12 pins for addressing. But there is also another pin.

This is the Chip Select pin (or similarly named).

So, since you need 16 chips, how do you select which chip gets the data?

Well, since 12 bits of the address are needed by the chip itself, and the CPU only has 16 bits, you have 4 more bits to represent which actual chip you want to select.

Note that 2^4 is 16.

So, in this simple case, you would need logic that take in the 4 upper bits of the address, and fans those out in to 16 distinct lines, one to the Chip Select pins on each of the 16 RAMs. This circuit is sometime known as a demultiplexer, or a decoder.

The 74138 is an example of such a decoder on a chip, it takes 3 inputs, and had 8 output (2^3 == 8). Each unique combination of input signals lights up 1, and only 1, of the output signals.

Now as things get finer grained, smaller blocks of memory (like devices that only need, say, 8 bytes of memory space), the logic gets more complicated.

On the other side of the coin, you can see if you had 32K of RAM and 32K of ROM, the top bit can be used. You could wire the bit straight to the 32K ROM (which is the top half of memory), and the other directly to a 32K RAM chip, but through an inverter. Simple logic.

Garth laughs when I mention Karnaugh maps, but these were the technique I was taught for trying to simplify logic like this. You create effectively truth tables of what goes in, and what you want out, and then apply some techniques to simplify it, and in the end you get the collection of logic operations (AND, OR, NAND, NOR, EOR) to get the desired outputs for the desired inputs.

Not necessary for simply logic.

I would just add:

• It's not necessary to decode addresses that aren't being used.
  
• It's ok to have a wider address range allocated for something than it uses, for example 256 addresses for a 6522 that only needs 16, unless it takes away valuable space in the memory map that you need as full of memory as you can possibly get it. (If you use a 4K RAM IC like in Mr. Hartung's example when when there are much bigger ones available, you probably won't be using a bunch of them, and it's probably fine to not decode all of the four top address bits. An exception would be for example if you want 14*4K of ROM (using 7/8 of a 64KB ROM), 4K of RAM, leaving 4K space for I/O. The 74xx154 is a 4-to-16-line decoder.)
  
• it's ok to have something appear at many addresses, as long as your code never tries to use an address that would make two or more things try to talk on the bus at the same time, or and address that would make two or more things listen at the same time if that's not what you wanted (although I can think of examples where it might be harmless or even desirable to have two listen at once).
  
• Usually the finer you get the address decoding, the more the propagation delays will be, reducing the maxium speed you can run at.

I just looked it up on Wikipedia, and it seems to just be a truth table. I had some recollection that it was more complex. The table that's about 60% of the way down my address-decoding page shows the conditions for the individual address bits for the diagram above it.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

I learned the same technique in the introductory course for computer engineering, nearly 30 years ago. The simplifications jump out visually in two dimensions, and seem more self-evident than the algebraic methods. Of course, it's an "old-school" technique, and resides in the same part of my brain as long-division ... some dust and cobwebs over there.

Mike

Here's the table I developed for POC V1. Truth tables are very useful for this sort of thing. Better to debug your logic on paper than in a DOA device.

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!

Did you actually read the article?
It's not just a truth table.

You're right. Nope, I didn't. I'm bad. I barely scanned it. Now I've read it, but only very quickly, and in the parts I do understand, it seems like they're doing it the hard way, although maybe it's just one of those things that's simple to understand yet hard to express.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

I think that has more to do with Wikipedia than Karnaugh maps

I saw a good page somewhere but I can't remember where.

this appears reasonably straight forward

http://www.ee.surrey.ac.uk/Projects/Labview/minimisation/karnaugh.html

Karnaugh maps can be useful, but you can't rely on them too much. More than 4 input variables becomes unwieldy, and they only provide the optimal solution in terms of AND/OR/NOT. Looking at a Karnaugh map, it's not immediately obvious when it's better to use an XOR gate for instance. Also, Karnaugh maps can only do one output, so if you have multiple outputs, with a possibility to share some logic, they don't help much. And of course, real world gates are different. Sometimes there's a limitation (you only have 3 NAND gates left), and sometimes there's better stuff (like a 3->8 decoder chip).

So, Where Do The Actual Addresses Come In

_________________
JMP $FFD2

The address lines are set by your CPU.

If we take the 6502 as example, on a power on or a reset situation the following happens:

1) The CPU sets the address lines to $FFFC and after that it performs a READ operation to get the byte stored at $FFFC
2) After that the CPU sets the address lines to $FFFD to read the second byte.
The data stored at $FFFC and $FFFD is called reset vector and it tells the CPU where to start the execution of the next commands.
The 6502 uses different devices such as RAM, ROM, I/O-Devices that are all connected to the same bus. 16 address lines and 8 data lines.
All these devices have at least one additional input called "chip select". Normally this input is low-active, that means, that if this input is LOW, the device is activated.
The problem is, that only one device can be active on the bus at a time and the others have to wait. So you need some "logic" to tell a device that is has to read or write data from / to the databus.
And this is the point where address-decoding is needed.
Lets go back to the reset condition on out 6502 CPU. It tries to read from $FFFC and $FFFD. These information are normally stored in a ROM. Lets say, we have a 8k EEPROM that contains the reset vector and some code to execute. Additionally we have a 8k RAM that the program on the ROM uses to store volatile data. The CPU does not no if the address that is currently used is RAM or ROM, it only wants to read or write data.
An easy approach for address decoding is to split the 64k possible memory that can be accessed by 16bit of the address bus into 8k blocks. Therefore a 74HC138 can be used. This chip has 3 inputs. With 3 inputs you can have 8 different combinations of "HIGH" and "LOW" you can set.
LOW LOW LOW
LOW LOW HIGH
LOW HIGH LOW
LOW HIGH HIGH
LOW LOW LOW
HIGH LOW HIGH
HIGH HIGH LOW
HIGH HIGH HIGH
The chip has 8 outputs, that correspond each to one of the combinations. On "LOW LOW LOW" the first output is set to LOW and all other outputs to HIGH. On "LOW LOW HIGH" the second output is set to LOW and all other to HIGH and so on. This is cool because we've learned that a chip-select is normally LOW-active.
What happens if we connect the last 3 lines of our address lines (A13,A14,A15) to this chip? We've divided our memory into 8 chunks of 8k each.
If the address lines are set between $0000 and $1fff, A13,A14 and A15 are all "LOW". That causes the first output of the 74HC138 to be LOW. If this output is connected to the "/CS" (means low active chipselect) of and 8k RAM chip, the chip well be activated every time the first 8k of memory are addressed. If you now connect the other 13 address lines (A0-A12) to the address lines of the RAM chip and the data-lines (D0-D7) to the data lines (plus the R/W signal from the CPU to distinguish between read and write) your CPU has access to your memory.
If you connect the last output of the 74HC138 to the /CS of your ROM chip too, then this chip is activated every time an address from $E000 to $FFFF is set on the address bus, but not the RAM chip in this case, because the first output of the 74HC138 is "HIGH" at this moment.
Address decoding is basically used to take care that only one chip is active. There are a lot of logic circuits you can use to divide your address space into all the pieces you need, even in parts of different size.

Hope that helps to get it more clear. Understanding what address-decoding is and how it works was a keypoint for me to build my "MOUSE"

Mario.

_________________
How should I know what I think, until I hear what I've said.

Hi, James.

In a simple system like the one you or I would build, the binary 16-bit address comes 'from' the CPU's address bus, and goes 'into' your address decode logic. Your address decode logic uses all or part of this address to decide which device (ROM, RAM, I/O) should be enabled, thereby allowing it to communicate with the CPU over the 8-bit data bus. More than one device can be 'listening' to the data bus at the same time, but allowing more than one device to 'talk' simultaneously fouls the works.

If Garth's excellent primer doesn't sink in, for whatever reason, you could try studying this simple example here.

Take care,

Mike