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

Question

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 address: 13
 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.

Answer 1

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!)

Answer 2

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.

Answer 3

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) {
  int r1, data, read1, read2;
  r1 = dataindex / 4 * 5; // the base of the read bank
  read1 = EEProm[r1 + dataindex % 4];
  read2 = EEProm[r1 + 4];
  // clear out the irrelevant data
  read2 >>= ((dataindex % 4) * 2);
  read2 &= 0x3;
  // combine the data      
  data = read1 + (read2 << 8);
  return data;
}

static void write(int data, int dataindex) {
  int r1;
  char read, towrite, mask;
  r1 = dataindex / 4 * 5; // the base of the write bank
  // fetch from the EEProm to not overwrite previous data
  read = EEProm[r1 + 4];
  // 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 &= ~mask; // clear the old data
  read |= towrite; // write the new data
  // write the data
  EEProm[r1 + dataindex % 4] = (char)(data);
  EEProm[r1 + 4] = read;
}

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.