Hadamard code

trasformata che mappa un messagio di lunghezza n su una matrice di dimensione 2^(n-1), rileva 2^(n-2) errori e ne corregge 2^(n-3)

perche il codice sia lineare e' necessario che n sia una potenza di 2

due righe della matrice differiscono in n/2 posizioni

// Hadamard codec - gnugo@hacari.org - 06/2012

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

uint8_t BlockDecodeChar(int16_t *DataMatrix, uint16_t HadamardCodeSize);
void BlockEncodeChar(int16_t *DataMatrix, uint8_t Input, uint16_t HadamardCodeSize);

void main(void){  
   uint16_t HadamardCodeSize, 
     BitsPerModulationSymbol, 
     ModulationSymbols, 
     CharactersPerModulationBlock, 
     ModulationBlockSize;
   
   uint8_t BitsPerCharacter, 
     CharPosition;
   
   BitsPerCharacter = 7; // dimensione singolo dato in ingresso
   HadamardCodeSize = 1 << (BitsPerCharacter - 1); // dimensione  del singolo codice hadamard in uscita 2^(n-1)
   
   BitsPerModulationSymbol = 6; // bit rappresentati da un simbolo della modulazione
   ModulationSymbols = 1 << BitsPerModulationSymbol; // dimensione alfabeto modulato
   
   CharactersPerModulationBlock = BitsPerModulationSymbol; // caratteri in un blocco modulazione
   ModulationBlockSize = BitsPerModulationSymbol * HadamardCodeSize; // dimensioni blocco modulazione
   
   printf("HadamardCodeSize %u\n", HadamardCodeSize);  
   printf("ModulationSymbols %u\n", ModulationSymbols);  
   
   // buffer matrici 
   int16_t *FHT_Buffer;
   FHT_Buffer = malloc(HadamardCodeSize*sizeof(int16_t));

   // buffer modulazione 
   int16_t *ModulationSymbolsBuffer;
   ModulationSymbolsBuffer = malloc(HadamardCodeSize*sizeof(int16_t));

   // dato in ingresso
   unsigned char InString[16];
   strcpy(InString,"ciao mondo");  
   
   // impacchetta un modulation block
   for (uint8_t CharPosition = 0; CharPosition < BitsPerModulationSymbol; CharPosition++){
      printf("encoding char %c pos %d\n", InString[CharPosition], CharPosition);
      BlockEncodeChar(FHT_Buffer, InString[CharPosition], HadamardCodeSize);      
      OrthogonalPack(FHT_Buffer, ModulationSymbolsBuffer, CharPosition, HadamardCodeSize);
   }

   // pulisci buffer
   memset(FHT_Buffer, 0, HadamardCodeSize*sizeof(int16_t));
   printbuf(ModulationSymbolsBuffer, HadamardCodeSize, 8);
   
   //ModulationSymbolsBuffer[15] = ModulationSymbolsBuffer[25];
   //ModulationSymbolsBuffer[19] = ModulationSymbolsBuffer[22];
   
   // disimpacchetta un modulation block
   for (uint8_t CharPosition = 0; CharPosition < BitsPerModulationSymbol; CharPosition++){
      OrthogonalUnPack(FHT_Buffer, ModulationSymbolsBuffer, CharPosition, HadamardCodeSize);
      
      uint8_t OutChar;
      OutChar = BlockDecodeChar(FHT_Buffer, HadamardCodeSize);
      
   }
}

// Forward Fast Hadamard Transform
void FastHadamardTransform(int16_t *Data, uint16_t Len){ 
   int16_t Bit1, Bit2, NewBit1, NewBit2 = 0;
   for (uint16_t Step = 1; Step < Len; Step <<= 1) {
      for (uint16_t Ptr = 0; Ptr < Len; Ptr += (Step << 1)) { 
	 for (uint16_t Ptr2 = Ptr; Ptr2 - Ptr < Step; ++ Ptr2) {
	    Bit1       = Data[Ptr2];  
	    Bit2       = Data[Ptr2+Step];
	    NewBit1    = Bit2; 
	    NewBit1   += Bit1;
	    NewBit2    = Bit2; 
	    NewBit2   -= Bit1;
	    Data[Ptr2] = NewBit1;
	    Data[Ptr2+Step]=NewBit2;
	 }
      }
   }
}	

// Inverse Fast Hadamard Transform
void InverseFastHadamardTransform(int16_t *Data, uint16_t Len){
   int16_t Bit1, Bit2, NewBit1, NewBit2 = 0;
   for (uint16_t Step = (Len >> 1); Step; Step >>= 1) {
      for (uint16_t Ptr = 0; Ptr < Len; Ptr += (Step << 1)) {
	 for (uint16_t Ptr2 = Ptr; Ptr2 - Ptr < Step; ++ Ptr2) {
	    Bit1               = Data[Ptr2];
	    Bit2               = Data[Ptr2 + Step];
	    NewBit1            = Bit1;
	    NewBit1            -= Bit2;
	    NewBit2            = Bit1;
	    NewBit2            += Bit2;
	    Data[Ptr2]         = NewBit1;
	    Data[Ptr2+Step] = NewBit2;
	 }
      }
   }
}

void printbuf(int16_t *Data, uint16_t Len, uint16_t Step){
   for(uint16_t i=0; i<Len; i++){
      if(i % (Step)== 0) printf("\n");
      printf("%d\t",Data[i]);
   }
   printf("\n");
}

// genera block code FEC
void BlockEncodeChar(int16_t *DataMatrix, uint8_t Input, uint16_t HadamardCodeSize){
   // pulisci buffer
   memset(DataMatrix, 0, HadamardCodeSize*sizeof(int16_t));

   // inserimento carattere nella matrice, alti negativi, bassi positivi
   // il valore massimo del dato e' 2 * size(matrice)
   if(Input < (HadamardCodeSize * 2)){
      if (Input < HadamardCodeSize) DataMatrix[Input] = 1;
      else DataMatrix[Input - HadamardCodeSize] = -1;
   }
   
   // codifica
   InverseFastHadamardTransform(DataMatrix, HadamardCodeSize);  
   
   // printbuf(FHT_Buffer,HadamardCodeSize,BitsPerCharacter);            
   //    
   // riduci a binario
   for (uint16_t TimeBit = 0; TimeBit < HadamardCodeSize; TimeBit++){
      if(DataMatrix[TimeBit] < 0) DataMatrix[TimeBit] = 0;
   }
}

// decodifica block code FEC
uint8_t BlockDecodeChar(int16_t *DataMatrix, uint16_t HadamardCodeSize){
   for (uint16_t TimeBit = 0; TimeBit < HadamardCodeSize; TimeBit++){
      if(DataMatrix[TimeBit] == 0) DataMatrix[TimeBit] = -1;
   }
   
   // decodifica
   FastHadamardTransform(DataMatrix, HadamardCodeSize);
   
   // printbuf(DataMatrix,HadamardCodeSize,BitsPerCharacter);                  
   // estrae dalla matrice
   int16_t Peak = 0;
   uint8_t PeakPos = 0;
   uint16_t SqrSum = 0;
   for (uint8_t TimeBit = 0; TimeBit < HadamardCodeSize; TimeBit++){
      int16_t Signal = DataMatrix[TimeBit];
      SqrSum += Signal * Signal;
      if (fabs(Signal) > fabs(Peak)){
	 Peak = Signal;
	 PeakPos = TimeBit;
      }
   }
   
   uint8_t OutChar = PeakPos;
   if (Peak < 0) OutChar += HadamardCodeSize;
   SqrSum -= Peak * Peak;
   printf("OutChar %c (Peak %d, PeakPos %d, SqrSum %d)\n", OutChar, Peak, PeakPos, SqrSum);
   return OutChar;
}

// todo: rotazione posizione carattere, altrimenti un fischio distrugge un carattere

// impacca con alfabeto ortogonale a tempo
void OrthogonalPack(int16_t *DataMatrix, int16_t *ModulationSymbolsBuffer, uint8_t CharPosition, uint16_t HadamardCodeSize){
   for (uint8_t TimeBit = 0; TimeBit < HadamardCodeSize; TimeBit++){ 
      ModulationSymbolsBuffer[TimeBit] |= (DataMatrix[TimeBit] << CharPosition);
   }
}

// disimpacca con alfabeto ortogonale a tempo
void OrthogonalUnPack(int16_t *DataMatrix, int16_t *ModulationSymbolsBuffer, uint8_t CharPosition, uint16_t HadamardCodeSize){
   for (uint8_t TimeBit = 0; TimeBit < HadamardCodeSize; TimeBit++){ 
      DataMatrix[TimeBit] = (ModulationSymbolsBuffer[TimeBit] >> CharPosition) & 0b1;
   }
}