# modulus to find 10-bit samples in 8-bit memory

For one of my electronics projects I am using an EEPROM chip that holds up to 512k bits of information, arranged in 8-bit (1 Byte) address registers. Multiply 512 x 1024 and divide by 8 and you'll get 65,536 Bytes.

Using 8 bits I can store a binary value from 0 to 255 in any one of those 65,536 address registers.

However, the values I'm interested in storing are not 8-bit but 10-bit. These 10-bit values are voltage samples taken from an Analog-to-Digital converter inside a microcontroller.

What I'm doing now is to use two addresses to store the 10-bit samples, like so:

This allows me to store 32,768 10-bit samples, but I can see there is a lot of wasted space.

Ideally I would like to use every bit of available memory storage and store the samples in sequential form like this:

In order to randomly store or read one of those 10-bit samples I am wondering if there is a way to calculate the start and end memory and bit positions for any given sample.

Example:

sample 12

start byte: 6


sorry, samples I counted from 1 and bit and memory addresses from 0

Obviously every sample always overlaps two memory addresses but I can't figure out how to apply the modulus to this problem and/or whether I need additional arithmetic to work it out.

To me it looks like there are two or maybe three moduluses (-ii?) that apply here, one of size 8 to get the bit positions and one of size 5 as the bits repeat on the same position after 5 address locations. Or do I need to do a mod 10 because it's ending on an odd address?

I've tried several things in a spreadsheet but I cannot seem to get a sequence that fits the addresses.

Some of my calculations went something like:

- sample * 1.2
- round up to whole number
- add one if number from step 1 and 2 are the same
- modulus(10) of the previous step
- hope the result is the memory address of this sample


I better end my embarrassing attempt here..

What I'm after are functions (for lack of a better word) that can do this:

 startAddress=findBeginAddress(sampleNr)
startBit=findBeginBit(sampleNr)


Once I know at what address and bit the sample starts I should be able to work out where the 10 bit sample stops.

I know beggers can't be choosers but the solution that works the fastest (in terms of processor steps) would be the clear winner.

EDIT: added 'and divide by 8' in the first paragraph for better clarity.

• 512kbits = (512 x 1024 = ) 524,288 bits. Divide that by 8 and you have Bytes, so 524,288 / 8 = 65,536 Bytes. Divide that by 1024 to get kBytes, so 65,536 / 1024 = 64kBytes. – captcha Mar 3 '15 at 20:56
• @DanielV Think I spotted the area of confusion, updated the first paragraph. Thanks for pointing it out. – captcha Mar 3 '15 at 21:46

Here's one approach. Let's say you want to find the beginning of sample $k$.

There are $k-1$ samples ahead of this sample, and hence $10(k-1)$ bits. Thus you want to find the position of the $10(k-1)+1=(10k-9)$th bit.

Write $10k-9=8q+r$ where $q=\lfloor \frac{10k-9}{8}\rfloor$ and $r=(10k-9)\% 8$ (i.e., quotient and remainder in dividing $10k-9$ by $8$).

Then $q$ will give the row number, and $r-1$ will give the bit number. (I think this takes into account that you start your addressing with $0$.) Note that $r$ is always odd, so $r-1$ never puts you in the previous row.

Example: Find (the beginning of) sample $7$.

$10\cdot 7-9=61=8\cdot 7+5$. Sample $7$ should start in row $7$, bit $4$. (With row and bit numbering starting at $0$ as in the helpful chart you provided with the question!)

• I'm glad my question made sense and it seems you've come up with a seemingly easy to understand solution. I will have to code it (and the other solutions provided below) to see how well it performs when running. But it is very promising nonetheless. – captcha Mar 3 '15 at 21:00

I am going to start numbering the samples from $0$, because it is easier, but I will be addressing memory as per your diagram. The bit at address $a$ and bit $b$ will we written as $(a,\ b)$.

To find out the location of the $n^\text{th}$ sample, we need to find $x = \lfloor{\frac{n}{4}\rfloor}$ and $y = (n \pmod 4)$ (both of these are not too costly, processor-wise). The starting location is then $(5x + y,\ 2y)$. The ending location is $(5x + y + 1,\ 2y + 1)$ which is just one more than both the co-ordinates for the starting location. Note that the bit at the ending location is the last bit of the sample (i.e., the range in inclusive).

To make this fast, consider using an integer to store the result of $\frac{n}{4}$ so it will automatically be truncated. You can also have a function that counts $10$ upward from a given $(a,\ b)$, incrementing $a$ by $1$ every time $b$ crosses $7$, which would save you unnecessary 'end location' code and avoid having to pass back a whole struct (I assume that's what you will be using for the address locations) in function calls.

• Many thanks for providing yet another method to tackle the problem. I wonder what those square brackets are you're using (around n/4). Not sure if I'll be doing structs yet but it'll be running on an AVR ATtiny84 microcontroller. In any case I'll have to spend some time deciphering all these answers and see how I can put this in code. It'll be fun! :) – captcha Mar 3 '15 at 21:28
• The square brackets used in all of these answers indicate 'floor' which is the largest integer less than a given number. For example, $\lfloor 4.27\rfloor = 4$ (I am just removing the part after the decimal point). This is easy to do in code; in C, you can assign 4.27 to an int and it will become 4 automatically. I have used AVRs myself (the ATmegas) and structs don't require too much extra code. If you want to avoid structs entirely, you could convert $(a,\ b)$ to $8b+a$ when passing it back from a function and then extract the two values by dividing and checking the quotient and remainder. – shardulc says Reinstate Monica Mar 4 '15 at 12:03
• Ah, I get it, Thanks. I know most of the software side of things but I'm struggling with many math notations. Interesting you're familiar with the AVR's I'm intending to use the ATtiny84 for the bulk of the processing. Project page here: marcelpost.com/wiki/index.php/Mcu_0084-voltage-datalogger – captcha Mar 4 '15 at 23:56
• If you want fast and efficient code for this (including the math), you could post a question on stackoverflow.com stating what exactly you want to do. You'll probably get the 'fastest' answers there. – shardulc says Reinstate Monica Mar 5 '15 at 11:16

An easier layout to code for would be

$$\begin{array}{c| c|c|c|c|c|c|c|c} \hline 0x0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0x1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0x2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 \\ 0x3 & 3 & 3 & 2 & 3 & 3 & 3 & 3 & 3 \\ \hline 0x4 & 0 & 0 & 1 & 1 & 2 & 2 & 3 & 3 \\ \hline 0x5 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 \\ 0x6 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 \\ \vdots \end{array}$$

And you only need to retrieve the bytes at location $\left\lfloor \frac x4 \right\rfloor \times 5 + \bigg(x {~\rm mod~} 4\bigg)$ and $\left\lfloor \frac x4 \right\rfloor \times 5 + 4$.

Read/Write code would be something like

static int read(int dataindex) {
r1 = dataindex / 4 * 5; // the base of the read bank
read1 = EEProm[r1 + dataindex % 4];
// clear out the irrelevant data
read2 >>= ((dataindex % 4) * 2);
// combine the data
return data;
}

static void write(int data, int dataindex) {
int r1;
r1 = dataindex / 4 * 5; // the base of the write bank
// fetch from the EEProm to not overwrite previous data
// setup the 2 bits to be written
towrite = (data>>8); // the 2 bits...
towrite <<= ((dataindex % 4) * 2); // slide them in place
mask = 0x3 << ((dataindex % 4) * 2);
read |= towrite; // write the new data
// write the data
EEProm[r1 + dataindex % 4] = (char)(data);
}


The only reason I can think to do it the other way would be if the EEPROM had a 16 bit interface, making it faster to fetch 2 adjacent bytes. Otherwise, just keep it simple for the sake of those who will follow you.

• The EEPROM is communicating over I2C, a simple two-channel interface (one is clock, the other is data), so it's all sequential access. Great alternative to using the registers btw, I did think of that too, but wouldn't there be a (tiny) bit of unused space at the very end if there isn't a full 10-address block for the last 8 samples? The other remark I can think of is the number of addresses that need to be queried. For every write I need to fill 10 memory addresses. It seems that there may be quite a bit of overhead. But I'll try and find out. Thanks! – captcha Mar 3 '15 at 21:05