Hadamard code: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
(2 intermediate revisions by one other user not shown) | |||
Line 1: | Line 1: | ||
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) | 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 | perche il codice sia lineare e' necessario che n sia una potenza di 2 | ||
due righe della matrice differiscono in n/2 posizioni | 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 | |||
<source lang="C"> | <source lang="C"> | ||
Line 14: | Line 18: | ||
#include <stdio.h> | #include <stdio.h> | ||
uint8_t BlockDecodeChar(int16_t *DataMatrix | uint8_t BitsPerModulationSymbol, | ||
void BlockEncodeChar(int16_t *DataMatrix, uint8_t Input, | 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){ | 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 | // pulisci buffer | ||
memset(FHT_Buffer, 0, HadamardCodeSize*sizeof(int16_t)); | memset(FHT_Buffer, 0, HadamardCodeSize*sizeof(int16_t)); | ||
printbuf(ModulationSymbolsBuffer, | 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 | 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 | // Forward Fast Hadamard Transform | ||
void FastHadamardTransform(int16_t *Data | void FastHadamardTransform(int16_t *Data){ | ||
int16_t Bit1, Bit2, NewBit1, NewBit2 = 0; | int16_t Bit1, Bit2, NewBit1, NewBit2 = 0; | ||
for (uint16_t Step = 1; Step < | for (uint16_t Step = 1; Step < HadamardCodeSize; Step <<= 1) { | ||
for (uint16_t Ptr = 0; Ptr < | for (uint16_t Ptr = 0; Ptr < HadamardCodeSize; Ptr += (Step << 1)) { | ||
for (uint16_t Ptr2 = Ptr; Ptr2 - Ptr < Step; ++ Ptr2) { | for (uint16_t Ptr2 = Ptr; Ptr2 - Ptr < Step; ++ Ptr2) { | ||
Bit1 = Data[Ptr2]; | Bit1 = Data[Ptr2]; | ||
Line 95: | Line 126: | ||
// Inverse Fast Hadamard Transform | // Inverse Fast Hadamard Transform | ||
void InverseFastHadamardTransform(int16_t *Data | void InverseFastHadamardTransform(int16_t *Data){ | ||
int16_t Bit1, Bit2, NewBit1, NewBit2 = 0; | int16_t Bit1, Bit2, NewBit1, NewBit2 = 0; | ||
for (uint16_t Step = ( | for (uint16_t Step = (HadamardCodeSize >> 1); Step; Step >>= 1) { | ||
for (uint16_t Ptr = 0; Ptr < | for (uint16_t Ptr = 0; Ptr < HadamardCodeSize; Ptr += (Step << 1)) { | ||
for (uint16_t Ptr2 = Ptr; Ptr2 - Ptr < Step; ++ Ptr2) { | for (uint16_t Ptr2 = Ptr; Ptr2 - Ptr < Step; ++ Ptr2) { | ||
Bit1 = Data[Ptr2]; | Bit1 = Data[Ptr2]; | ||
Line 122: | Line 153: | ||
// genera block code FEC | // genera block code FEC | ||
void BlockEncodeChar(int16_t *DataMatrix, uint8_t Input | void BlockEncodeChar(int16_t *DataMatrix, uint8_t Input){ | ||
// pulisci buffer | // pulisci buffer | ||
memset(DataMatrix, 0, HadamardCodeSize*sizeof(int16_t)); | memset(DataMatrix, 0, HadamardCodeSize*sizeof(int16_t)); | ||
Line 134: | Line 165: | ||
// codifica | // codifica | ||
InverseFastHadamardTransform(DataMatrix | InverseFastHadamardTransform(DataMatrix); | ||
// printbuf(FHT_Buffer,HadamardCodeSize, | // printbuf(FHT_Buffer,HadamardCodeSize,BitsPerInput); | ||
// | // | ||
// riduci a binario | // riduci a binario | ||
Line 145: | Line 176: | ||
// decodifica block code FEC | // decodifica block code FEC | ||
uint8_t BlockDecodeChar(int16_t *DataMatrix | uint8_t BlockDecodeChar(int16_t *DataMatrix){ | ||
for (uint16_t TimeBit = 0; TimeBit < HadamardCodeSize; TimeBit++){ | for (uint16_t TimeBit = 0; TimeBit < HadamardCodeSize; TimeBit++){ | ||
if(DataMatrix[TimeBit] == 0) DataMatrix[TimeBit] = -1; | if(DataMatrix[TimeBit] == 0) DataMatrix[TimeBit] = -1; | ||
Line 151: | Line 182: | ||
// decodifica | // decodifica | ||
FastHadamardTransform(DataMatrix | FastHadamardTransform(DataMatrix); | ||
// estrae dalla matrice | // estrae dalla matrice | ||
int16_t Peak = 0; | int16_t Peak = 0; | ||
Line 174: | Line 204: | ||
} | } | ||
// | // 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 | 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); | |||
} | } | ||
} | } | ||
</source> | </source> |
Latest revision as of 10:21, 3 July 2012
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); } }