How to efficiently encode this?

Question

I have 5 ring oscillators whose frequencies are f1, f2, ..., f5. Each ring oscillator (RO) has 5 inverters. For each RO, I just randomly pick 3 inverters out of 5 inverters. For example, in RO1, I pick inverter 1,3,5 (Notation: RO1(1,3,5)). So I have the following:

RO1(1,3,5) (I call this is the configuration of RO1)

RO2(1,2,4) (configuration of RO2)

RO3(2,4,5)

RO4(1,4,5)

RO5(2,3,4)

Let say f1 < f3 < f4 < f5 < f2 (I call this is a rank). So for this particular rank, I have:

{RO1(1,3,5), RO3(2,4,5), RO4(1,4,5), RO5(2,3,4), RO2(1,2,4)}

For a different rank, let say f1 < f2 < f3 < f4 < f5, I will have:

{RO1(1,3,5), RO2(1,2,4), RO3(2,4,5), RO4(1,4,5), RO5(2,3,4)}

So as you can see, the rank affects how things are arranged.

One trivial encoding is:

{RO1(1,3,5), RO3(2,4,5), RO4(1,4,5), RO5(2,3,4), RO2(1,2,4)} = 000...00 (all zeros)

{RO1(1,2,5), RO3(2,4,5), RO4(1,4,5), RO5(2,3,4), RO2(1,2,4)} = 000...01 (all zeros with a single 1)

etc ... (repeat the whole process until we exhaust all combinations for all configurations for all ranks).

This trivial encoding is NOT efficient because I need to store the entire mapping table in memory so that later on, I can use it for encoding.

My question is: Is there a better way to carry out the encoding without having access to the entire mapping table?

Clarification: For 5 ROs, there are 5! different possible ranks. So I will need ceiling(log(5!))=7 bits (log here is base-2) to encode 5! different ranks.

Each RO has (5 choose 3) different possible configurations. So for 5 ROs, there are (5 choose 3)^5=10^5 possible configuration combinations. Therefore, I will need ceiling(log(10^5))=17 bits to encode all possible combinations.

So let me re-state my question in a clearer way: Given a specific rank of 5 ROs and the configurations of 5 ROs, how can I efficiently encode those information into 24 bits?

Answer 1

Yes, there is. One such encoding follows.

To encode the rank, write out the order of the frequencies as bytes. For example, $f_1 < f_3 < f_4 < f_5 < f_2$ becomes

$$ 00000001\ 00000011\ 00000100\ 00000101\ 00000010. $$

To encode the configuration of each RO, put a $1$ in the $i^\text{th}$ position if inverter $i$ is one of the 3 inverters you picked, and $0$'s elsewhere. For example,

• $\operatorname{RO}_1(1,3,5)$ becomes $10101000$,
• $\operatorname{RO}_2(1,2,4)$ becomes $11010000$.

Now stick the bytes together end-to-end, so that you have a 10 byte sequence. Using your example of $(\operatorname{RO}_1(1,3,5), \operatorname{RO}_3(2,4,5), \operatorname{RO}_4(1,4,5), \operatorname{RO}_5(2,3,4), \operatorname{RO}_2(1,2,4))$, you'll get the following encoding: (ignore the line break)

$$ 00000001\ 00000011\ 00000100\ 00000101\ 00000010\\ 10101000\ 11010000\ 01011000\ 10011000\ 01110000. $$

Of course, your choice of encoding will depend on what you're doing with the data. Hopefully this was enough to get you started.

Answer 2

To encode a permutation into a number, you can use the factoradic base. A factoradic representation of a positive integer $x$ is the unique sequence of digits $d_n..d_0$ such that each digit $d_n$ is at most $n$ and the sum $\sum_{i=0}^{n}(i!\,d_i) = x$

To encode a permutation word into a factoradic number, you could represent each symbol of the word by the digit $d$ if it's the $d^\text{th}$ symbol in the alphabet not used yet, but this could get hard to implement, both in hardware and in software. Instead, I suggest using the Fisher-Yates shuffle. To encode:

• represent the input word as an array a of numbers from 0..n
• for each number a_i from n downto 0
  • find the leftmost index i of the number a_i in a
  • store a[i] into a[a_i]
  • push i into the output, most significant digit first

To decode:

• initialize a as an array of n elements

• for each index i from 0 to n

  • store a[input[i]] into a[i], where input[0] is the least significant digit (0) of the input, unless input[i] == i

  • store i into a[input[i]]

    these two steps are equivalent to initialising a[i] to i and swapping it with a[input[i]]

• output the resulting array a

Translating these into a hardware circuit produces a 2D grid of 3-bit constant comparators, 2-way multiplexers, encoders and lots of wiring in case of the encoder, and a 2D grid of decoders, 2-way multiplexers, bigger multiplexers and lots of wiring in case of the decoder.

You can encode a 5-digit factoradic number into 7 bits by calculating its value, but if arithmetic is expensive you can also just store: $a_0$ is always zero; $a_1$ as one bit; $a_3$ as two bits; $a_2$ and $a_4$ as a four-bit value. Or you could store the number each digit separately. These then pack nicely into a byte. But this costs us an extra bit, which is a luxury we don't have.

---

To encode a $\binom{5}{3}$ selection into 4 bytes, you could use (five times) a lookup table. It's just 10 terms, after all. Moreover 4->4 LUTs are the building blocks of FPGAs (and the fifth bit is just an NXOR of the remaining four). You could use arithmetic to represent the table implicitly, but this would end up much bigger in hardware (and you need even bigger LUTs anyways), and much less readable in software (and bigger).

This alone costs us 20 bits total (plus seven for the permutation), three more than is the budget. Two decades can be packed into seven bytes, but we're still one bit short. Three decades fit into ten bytes, so pack our decades by 2 and 3, resulting in the optimal amount.

You could use arithmetic to pack digits, but if you want to implement the packing in hardware, there is an alternative encoding, named "Densely Packed Decimals (DPD)". It passes numbers 0-79 unmodified, and it encodes two digits to seven bits or three digits to ten bits.

Assume the three digits are abcd efgh ijkm and their DPD encoding is pqr stu v wxy. Then

The encoding is:

  p = (a*f*i) + (a*j) + b
  q = (a*g*i) + (a*k) + c
  r = d
  s = (-a*e*j) + (f*-i) + (-a*f) + (e*i)
  t = (-a*e*k) + (a*i) + g
  u = h
  v = a + e + i
  w = (-e*j) + (e*i) + a
  x = (-a*k) + (a*i) + e
  y = m

The decoding is:

  a = (-s*v*w) + (t*v*w*x) + (v*w*-x)
  b = (p*s*x) + (p*-w) + (p*-v)
  c = (q*s*x) + (q*-w) + (q*-v)
  d = r
  e = (t*v*-w*x) + (s*v*w*x) + (-t*v*x)
  f = (p*t*v*w*x) + (s*-x) + (s*-v)
  g = (q*t*w) + (t*-x) + (t*-v)
  h = u
  i = (t*v*w*x) + (s*v*w*x) + (v*-w*-x)
  j = (p*-s*-t*w) + (s*v*-w*x) + (p*w*-x) + (-v*w)
  k = (q*-s*-t*v*w) + (q*v*w*-x) + (t*v*-w*x) + (-v*x)
  m = y

Herein is: * = AND, + = OR, - = NOT.

ref.: http://web.archive.org/web/20070824053303/http://home.hetnet.nl/mr_1/81/jhm.bonten/computers/bitsandbytes/wordsizes/ibmpde.htm#dense7

---

Note that if the ring oscillators are guaranteed to be different, the amount of possibilities shrinks from $2^16 < 10^5 < 2^17$ to just $2^7 < \binom{10}{5} = 212 < 2^8$. I wouldn't be afraid to spare an 8-bit lookup table for this.

also note that while we are a tiiiny bit over 47 bits at two messages, it is possible to save one bit out of 72 by packing three transmissions into one. It actually suffices to unpack (or to not pack) all three pairs of decades, and repack them as two triplets. You lose byte alignment (and base64-alignment), however.

It should also be possible to save an extra bit every ninth transmission, but don't ask me to do this in hardware. It's not too hard in software if your language supports arbitrary precision arithmetic, however.