Search code examples
c++cbinarylinear-algebrabitwise-operators

Binary change of basis in C/C++

I'm implementing a decoding method from an interface control document, and it requires a change of basis in binary - which is a first for me. The change of basis is as follows (z is what i have, the matrix is the transformation, and u is what I need):

enter image description here

and it states:

enter image description here

What I've tried is to multiply the z_n vector by each column of the transformation matrix (using and AND operator) and add the results (with an XOR operator), like this:

u = (z & base[0])^(z & base[1])^(z & base[2])^(z & base[3])^(z & base[4])^(z & base[5])^(z & base[6])^(z & base[7]);

where z is the binary number to be transformed (e.g. 10100101, or its representation as 8-bit int) and base are the columns of the transformation matrix represented as integers:

uint8_t base[8] = {155, 221, 62, 28, 55, 179, 96, 148};

But the results don't match with what it was supposed to be. Am I implementing this change of basis correctly?

Edit

I have the inverse transformation as well. If the implementation is correct, I should be able to transform a byte, and then transform it back to the original state. In my implementation, the back transformation yields a different result:

enter image description here

Problem solved. Here's the verification code:

#include <math.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*Base change*/
uint8_t const matrix[] = { 0xC5, 0x42, 0x2E, 0xFD, 0xF0, 0x79, 0xAC, 0xCC }; // the rows
uint8_t const matrixinv[] = {0x8D, 0xEF, 0xEC, 0x86, 0xFA, 0x99, 0xAF, 0x7B}; // the rows

uint8_t const z = 0x64;
uint8_t u, z2;


void main(){

    printf("initial value: %d ", z);
    u = 0;
    if (z & 0x80) u ^= matrix[0];
    if (z & 0x40) u ^= matrix[1];
    if (z & 0x20) u ^= matrix[2];
    if (z & 0x10) u ^= matrix[3];
    if (z & 0x08) u ^= matrix[4];
    if (z & 0x04) u ^= matrix[5];
    if (z & 0x02) u ^= matrix[6];
    if (z & 0x01) u ^= matrix[7];

    printf(" - forward result: %d ",u);

    z2 = u;
    u = 0;
    if (z2 & 0x80) u ^= matrixinv[0];
    if (z2 & 0x40) u ^= matrixinv[1];
    if (z2 & 0x20) u ^= matrixinv[2];
    if (z2 & 0x10) u ^= matrixinv[3];
    if (z2 & 0x08) u ^= matrixinv[4];
    if (z2 & 0x04) u ^= matrixinv[5];
    if (z2 & 0x02) u ^= matrixinv[6];
    if (z2 & 0x01) u ^= matrixinv[7];

    printf("back result: %d ",u);
    getchar();
}

initial value: 100  - forward result: 21 back result: 100
Solution

  • Your language supports vectorized two-operand XOR. It doesn't support horizontal XOR (parity calculation). So we'll structure our operations accordingly.

    Assuming

    uint8_t const matrix[] = { 0xC5, 0x42, 0x2E, 0xFD, 0xF0, 0x79, 0xAC, 0xCC }; // the rows
uint8_t const z;
uint8_t u;

    Your result is going to be

    u = 0;
if (z & 0x80) u ^= matrix[0];
if (z & 0x40) u ^= matrix[1];
if (z & 0x20) u ^= matrix[2];
// etc following the pattern
// if ((z << i) & 0x80) u ^= matrix[i];

    Note that I've assumed that the reversal of bit order between input and output is a mistake. If it's correct, you may need to mirror all the contents of matrix.