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

packing ortogonale ogni block code di un carattere viene associato a un bit del simbolo. in questo modo il carattere da trasmettere e' mappato nel domini odella frequenza, la sua rappresentazione come hadamard code nel dominio del tempo.

interleaving TODO

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

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

uint8_t BitsPerModulationSymbol, 
  AlphabetSize, 
  BitsPerInput, 
  HadamardCodeSize, 
  SymbolsPerHadamardCode, 
  HadamardCodesPerInterleaverBlock,
  InterleaverBlockSize,
  SymbolsPerInterleaverBlock;

uint8_t BlockDecodeChar(int16_t *DataMatrix);
void BlockEncodeChar(int16_t *DataMatrix, uint8_t Input);
uint8_t InterleaveBlock(uint8_t *InData, int16_t *DataMatrix, uint8_t *ModulationSymbolsBuffer);

void main(void){  
   // alfabeto
   BitsPerModulationSymbol = 4; // bit rappresentati da un simbolo della modulazione
   AlphabetSize = (1 << BitsPerModulationSymbol); // dimensione alfabeto modulato
   
   // FEC
   BitsPerInput = 4; // dimensione singolo dato in ingresso
   HadamardCodeSize = 1 << (BitsPerInput - 1); // dimensione  del singolo codice hadamard in uscita 2^(n-1)
   SymbolsPerHadamardCode = (HadamardCodeSize/BitsPerModulationSymbol);
   
   // interleaver
   HadamardCodesPerInterleaverBlock =  32; // per arrivare ai 128 voluti da aes
   InterleaverBlockSize  = (HadamardCodesPerInterleaverBlock * HadamardCodeSize); // dimensione del blocco di interleaving
   SymbolsPerInterleaverBlock = (SymbolsPerHadamardCode * HadamardCodesPerInterleaverBlock);
   
   // buffer matrici 
   int16_t *FHT_Buffer;
   FHT_Buffer = malloc(HadamardCodeSize*sizeof(int16_t));
   
   // buffer modulazione 
   uint8_t *ModulationSymbolsBuffer;
   ModulationSymbolsBuffer = malloc(SymbolsPerInterleaverBlock*sizeof(uint8_t));
   
   // caratteri in ingresso
   unsigned char InString[16] = { 0 };
   strcpy(InString,"ciao mondo cane");  
   
   // dati input codice FEC
   uint8_t InData[32] = { 0 };
   
   // dati out codice FEC
   uint8_t OutData[32] = { 0 };
   
   // caratteri in uscita
   unsigned char OutString[16] = { 0 };

   // ##################### //
     
   printf("# HadamardCodeSize %u\n", HadamardCodeSize);  
   printf("# AlphabetSize %u\n", AlphabetSize);  
   printf("# HadamardCodesPerInterleaverBlock %u\n", HadamardCodesPerInterleaverBlock);
   printf("# InterleaverBlockSize %u\n", InterleaverBlockSize);  
   printf("# SymbolsPerInterleaverBlock %u\n", SymbolsPerInterleaverBlock);  
    
   printf("In: %s\n", InString);

   // formatta dati in ingresso, lsnibble first
   for (uint8_t TimeBit = 0; TimeBit < 16; TimeBit++){
      InData[TimeBit * 2] |= InString[TimeBit] & 0b1111;
      InData[(TimeBit * 2) + 1] |= (InString[TimeBit] >> 4) & 0b1111;
   }
   
   InterleaveBlock(InData, FHT_Buffer, ModulationSymbolsBuffer);

   // pulisci buffer
   memset(FHT_Buffer, 0, HadamardCodeSize*sizeof(int16_t));
   printbuf(ModulationSymbolsBuffer, SymbolsPerInterleaverBlock, 8);

   // disturbo
   ModulationSymbolsBuffer[2] = 42;
   ModulationSymbolsBuffer[6] = 42;
   ModulationSymbolsBuffer[12] = 42;
   ModulationSymbolsBuffer[11] = 42;
   
   // deinterleave
   DeInterleaveBlock(OutData, FHT_Buffer, ModulationSymbolsBuffer);
   
   // formatta dati in uscita
   for (uint8_t TimeBit = 0; TimeBit < 16; TimeBit++){
      OutString[TimeBit] |= (OutData[TimeBit * 2] & 0b1111);
      OutString[TimeBit] |= (OutData[(TimeBit * 2) + 1] & 0b1111) << 4;
   }
   printf("Out: %s\n", OutString);
}

// Forward Fast Hadamard Transform
void FastHadamardTransform(int16_t *Data){ 
   int16_t Bit1, Bit2, NewBit1, NewBit2 = 0;
   for (uint16_t Step = 1; Step < HadamardCodeSize; Step <<= 1) {
      for (uint16_t Ptr = 0; Ptr < HadamardCodeSize; 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){
   int16_t Bit1, Bit2, NewBit1, NewBit2 = 0;
   for (uint16_t Step = (HadamardCodeSize >> 1); Step; Step >>= 1) {
      for (uint16_t Ptr = 0; Ptr < HadamardCodeSize; 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){
   // 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);  
   
   // printbuf(FHT_Buffer,HadamardCodeSize,BitsPerInput);            
   //    
   // 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){
   for (uint16_t TimeBit = 0; TimeBit < HadamardCodeSize; TimeBit++){
      if(DataMatrix[TimeBit] == 0) DataMatrix[TimeBit] = -1;
   }
   
   // decodifica
   FastHadamardTransform(DataMatrix);
   
   // 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;
}

// interleaving
uint8_t InterleaveBlock(uint8_t *InData, int16_t *DataMatrix, uint8_t *ModulationSymbolsBuffer){
   uint8_t BitPos, SymbolOffset, BitOffset;
   for (uint8_t FECBlock = 0; FECBlock < HadamardCodesPerInterleaverBlock; FECBlock++){
      
      BlockEncodeChar(DataMatrix, InData[FECBlock]);
      for (uint8_t FECBit = 0; FECBit < HadamardCodeSize; FECBit++){
	 BitPos = (FECBlock * HadamardCodeSize) + FECBit;
	 BitOffset = BitPos % BitsPerModulationSymbol;
	 SymbolOffset = ((FECBit * HadamardCodeSize) + FECBlock) % SymbolsPerInterleaverBlock;
	 ModulationSymbolsBuffer[SymbolOffset] |= (DataMatrix[FECBit] & 0b1) << BitOffset;
	 // printf("%u,%u,%u\n", SymbolOffset, BitOffset, BitPos);
      }
//      printf("\n in FEC: ");
//      printbuf(DataMatrix, HadamardCodeSize, 8);
   }
}

// deinterleaving
void DeInterleaveBlock(uint8_t *OutData, int16_t *DataMatrix, uint8_t *ModulationSymbolsBuffer){
   uint8_t BitPos, SymbolOffset, BitOffset;
   for (uint8_t FECBlock = 0; FECBlock < HadamardCodesPerInterleaverBlock; FECBlock++){
      // pulisci matrice
      memset(DataMatrix, 0, HadamardCodeSize*sizeof(int16_t));
      for (uint8_t FECBit = 0; FECBit < HadamardCodeSize; FECBit++){
	 BitPos = (FECBlock * HadamardCodeSize) + FECBit;
	 BitOffset= BitPos % BitsPerModulationSymbol;
	 SymbolOffset = ((FECBit * HadamardCodeSize) + FECBlock) % SymbolsPerInterleaverBlock;
	 DataMatrix[FECBit] |= ((ModulationSymbolsBuffer[SymbolOffset] & (0b1 << BitOffset)) >> BitOffset);
      }
//      printf("\n out FEC:\n");
//      printbuf(DataMatrix, HadamardCodeSize, 8);
      
      OutData[FECBlock] = BlockDecodeChar(DataMatrix);
   }
}