Hadamard code
Jump to navigation
Jump to search
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 la il codice sia lineare e' bene 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; } }