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 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);
}
}