кодирование

 
0
 
C++
ava
Vicipi | 18.01.2009, 10:31
у меня есть массив int M[96]; состоящий из 1 и 0.  дана матрица А=
      1101000
      0110100
      1110010
      1010001
нужно зашифровать массив путем разбиеня на 4 бита:
"кодирование сообщения из 4 бит кодом Хемминга осуществляется путем умножения вектора сообщения на порождающую матрицу кода в соответствии с алгоритмом
    Y = X A;
    где Х – вектор сегмента сообщения из 4 бит, Y – закодированный сегмент сообщения, содержащий 7 бит" smile 
пожете пояснить,  на что нужно умножать: 4 бита на строку или столбец матрицы?
брать вектор сегмента - это как? smile 

Ответы (15)
ava
mes | 18.01.2009, 18:29 #
ava
Vicipi | 18.01.2009, 22:50 #
информация полезная, но не помогла...
ava
Kallikanzarid | 19.01.2009, 06:09 #
Тут, видимо, синопсис такой: char values[n] - массив n векторов, values[i] = x1 * 2^4 + x2.
Умножать, понятное дело, можно только одним способом :)

Вот, я частично сделал:


#include <stdio.h>

unsigned char hamming( unsigned char x );
unsigned char unhamming( unsigned char x );

int main( int argc, char** argv) {
    unsigned int cur;
    
    if( argc != 1 || argv[1][0] != '-' || argv[1][1] != 'e' || argv[1][1] != 'd' ) {
        fputs( "Usage: \"hamming [-e/-d]\" to encode/decode input to output" );
        exit(1);
    }
    
    if( argv[1][1] == 'e' )
        while( ( cur = getchar() ) != EOF )
            printf( "%c%c", hamming( (unsigned char)x >> 4 ), hamming( (unsigned char)x & 0x0F ) );
    else
        while( ( cur = getchar() ) != EOF )
            printf( "%c%c", unhamming( cur ) << 4 + unhamming( getchar() ) );
}

/* translates one word (4 bits) of the input
* to the output hamming code suitable for
* transmitting as ascii string.
* for this purpose for the special symbols
* (0th to 31th and 127th) 8th bit is set
* so that they are processed well by text
* output system.
*
* TODO: check if I screwed up, +1 to your rep
* if you find my mistake here.
*/
unsigned char hamming( unsigned char x ) {
    static M[7] = { 1101b, 1110b, 0111b, 1000b, 0100b, 0010b, 0001b };
    int i;
    unsigned char result = 0;
    
    for( i = 0; i < 7; ++i )
        result += x & M[i];
    
    if( 32 <= result && result < 127 )
        return result;
    else
        return result & 10000000b;
}

/* reverses hamming encoding
* that's gonna be your homework :)
*/
unsigned char unhamming( unsigned char x ) {
    /* TODO:
     * 1) reverse selective last bit setting
     * 2) reverse matrix multiplication,
     *    you will have to solve linear system of algebraic equations.
     */
}


ava
GoldFinch | 19.01.2009, 07:36 #
разве такое не решается таблицей из 16 элементов7
ava
Vicipi | 19.01.2009, 20:02 #

values[i] = x1 * 2^4 + x2.
 
Что это?
ava
mes | 19.01.2009, 20:10 #
Цитата(Vicipi @  19.1.2009,  19:02 findReferencedText)
Что это? 

Это  "^"  ?  исключающее_или (xor) поиск поможет

Цитата(Vicipi @  18.1.2009,  09:31 findReferencedText)
дана матрица А=

матрица, имхо, неправильная, контрольные ряды должны распологаться по степеням двойки то есть ряды 1,2,4
а у Вас 1,2,3.

Цитата(GoldFinch @  19.1.2009,  06:36 findReferencedText)
разве такое не решается таблицей из 16 элементов7 

решается для кодирования. Но таблица не позволяет узнать в каком ряду ошибка.
ava
Vicipi | 19.01.2009, 20:26 #
Цитата(Vicipi @  19.1.2009,  20:02 findReferencedText)
Что это? 

в смысле что за формула такая, что за x1 и x2, для чего она?
ava
mes | 19.01.2009, 22:37 #
Цитата(Vicipi @  19.1.2009,  19:26 findReferencedText)
в смысле что за формула такая, что за x1 и x2, для чего она? 

а откуда она появилась то ? в приведенном коде не нашел.  smile 
ava
Vicipi | 20.01.2009, 22:01 #
Цитата(Kallikanzarid @  19.1.2009,  06:09 findReferencedText)
Тут, видимо, синопсис такой: char values[n] - массив n векторов, values[i] = x1 * 2^4 + x2.

до кода.
ava
mes | 24.01.2009, 00:28 #
Цитата(Vicipi(from pm))




вот умножили на матрицу H, получили синдром 24*3, как же он 4 бита возвращает?  инф.биты где смотреть, в каком массиве? 

короче я запуталась, можешь декодирование полностью описать..


4 бита никуда не деваются - они просто меняют свое положение в 7ми битной последовательности.
для начала как происходит это без участия матрицы :

4х битная последовательность данных :      b1,b2,b3,b4
7ми битная последовательность хемминга: r1,r2, i1, r3, i2, i3,i4


// кодирование :
// запоминаем сообщение в информационных битах :
i1   = b1;
i2   = b2;
i3   = b3;
i4   = b4;

// получаем контрольные биты :
r1   = b1^b2^b4;
r2   = b1^b3^b4;
r3   = b2^b3^b4;



декодирование:
получаем синдром:
s1 = r1^i1^i2^i4;
s2 = r2^i1^i3^i4;
s3 = r3^i2^i3^i4;


er = (s1<<2) | (s2<<1) | s1; // er = s1+s2*2+s3*4;

если er не ноль, то ошибка
  исправляем, инвертируя  бит с номером er-1 в хемминг-последовательности на противоположный

теперь последовательность хемминга востановлена, получаем наши биты

b1   = i1;
b2   = i2;
b3   = i3;
b4   = i4;

ava
mes | 24.01.2009, 00:45 #
матрица нужна , чтоб автоматизировать процесс ,
в ней выражено какие биты надо использовать для операций.

кодирование :


выразим матрицу для кодирования через неупакованную последовательность бит

    unsigned char M[7][4] = { { 1,1,0,1 }
                            , { 1,0,1,1 }                   
                            , { 1,0,0,0 }
                            , { 0,1,1,1 }                            
                            , { 0,1,0,0 }
                            , { 0,0,1,0 }
                            , { 0,0,0,1 }
                            };   

таким же образом определим исходное сообщение и хеминг последовательность

unsigned char data[4] = { ... };
unsigned char ham[7] = { 0 };

как в таблице пифагора 4 бита сообщения соотносятся с 7ю битами хемминга
чтоб получить бит N хемминга мы должны сложить по модулю 2 произведение каждого бита данных
на соответсвующий элемент матрицы, т.е :

ham[N] = (M[N][0] & data[0]) ^  (M[N][1] & data[1]) ^ (M[N][2] & data[2]) ^ (M[N][3] & data[3]);


если присмотреться к матрице ,  то видно что для информационых битов матрица единичная,
т.е в результате выполнения предыдущей операции
  для информационых битов происходит присваивание (к примеру i2 = b2)
а для контрольных вычесление четности (к примеру r3   = b2^b3^b4)

после мы будем использовать знание о четности для восстановления последовательности


декодирование :

прежде всего мы должны получить синдром по контрольным битам и если он не 0 то исправить последовательность

для этого заводим матрицу

    unsigned char S[7][3] = { { 1,0,0 }
                            , { 0,1,0 }                                             
                            , { 1,1,0 }                           
                            , { 0,0,1 }                             
                            , { 1,0,1 }
                            , { 0,1,1 }
                            , { 1,1,1 }
                            };

каждый вектор матрицы соответсвует битам
для вышеупомянутых операций  :
Цитата


s1 = r1^i1^i2^i4

s2 = r2^i1^i3^i4 

s3 = r3^i2^i3^i4


теперь делаем эти операции в цикле умножая на вектор матрицы

    unsigned char s[3] = {0};

    for( int j = 0; j < 3; ++j )    
       for( int i = 0; i < 7; ++i ) s[j] ^= ham[i] & S[i][j];

и вычисляем номер ошибочного разряда:

    for( int j = 0; j < 3; ++j )  er |=s[j]<<j; // можно и без цикла как было показано выше


Цитата


er = (s1<<2) | (s2<<1) | s1; // er = s1+s2*2+s3*4;



теперь если есть ошибка, то востанавливаем нашу последовательность :

    if (er) ham[er-1]^=1;  


теперь можно получить нужные нам биты, возпользуемся опять матрицей

умножаем каждый бит хеминга на соответствующий вектор матрицы
и XORим его

    unsigned char I[4][7] = { { 0,0,1,0,0,0,0 }
                            , { 0,0,0,0,1,0,0}                                             
                            , { 0,0,0,0,0,1,0 }
                            , { 0,0,0,0,0,0,1 }
                            }

    for( int j = 0; j < 4; ++j )    
       for( int i = 0; i < 7; ++i ) data[j] ^= ham[i] & I[j][i];


ava
mes | 24.01.2009, 01:06 #
Как уже было сказано выше, матрица нужна чтоб не зависить от порядка рассположения битов в последовательностях и способа расчета контрольной суммы.
Все три матрицы должны быть синхронизированны относительной общей схемы кодирования.

Расположение информационых и контрольных бит в последовательности хемминга тоже не случайно,
оно выбрано таким образом, чтоб по ошибке в контрольной сумме , можно было узнать номер испорченного бита

ну и напоследок тут подробно изложено по теме со схемами :
lib.aanet.ru/pdf/kafedra22/d2.pdf 
ava
mes | 24.01.2009, 01:35 #
Примечание:

сложение по модулю 2   аналогичнo   операции xor (^)
а умножение битов   аналогичнo   операции and (&)



ava
mes | 25.01.2009, 13:40 #
Цитата("Vicipi(pm)")


а как определить правильная матрица или нет?


протестить :)

Во первых:
Цитата(mes @  24.1.2009,  00:06 findReferencedText)
Все три матрицы должны быть синхронизированны относительной общей схемы кодирования.

Во вторых:
Цитата(mes @  23.1.2009,  23:45 findReferencedText)
матрица нужна , чтоб автоматизировать процесс , 

в ней выражено какие биты надо использовать для операций.


Порождающая матрица представляет формулу, которая кодируют контрольные биты так, чтоб ошибка четности, показывала испорченого номер бита
Также она показывает в каком месте будет располагаться биты сообщения.

для вышеупомянотого 7ми битного ряда хеминга :
Цитата


r1,r2, i1, r3, i2, i3,i4


порождаюшая матрица соответсвует как :


       1234 (b1 b2 b3 b4)
r1     1101   -> r1 = b1^b2^b4
r2     1011   -> r2 = b1^b3^b4                   
i1     1000   -> i1 = b1
r3     0111   -> r3 = b2^b3^b4                           
i2     0100   -> i2 = b2
i3     0010   -> i3 = b3
i4     0001   -> i4 = b4

матрица определения синдрома вычисляется из рядов порождающей  матрицы, соответсветсвующих контрольным битам
т.е 1, 2 и 4 строчкe. Чтоб получить синдром надо сложить контрольный бит с теми битами из которых он получен :

    1234      rr1r234  (r1,r2, i1, r3, i2, i3,i4)
r1  1101   -> 1010101  -> s1 = r1^i1^i2^i4
r2  1011   -> 0110011  -> s2 = r2^i1^i3^i4
r3  0111   -> 0001111  -> s3 = r3^i2^i3^i4


эта синдромная матрица соответсвует представленой выше но повернутой на 90 градусов.. принципиальной разницы нет.


ну а матрица получения битов даннов, получена таким же образом из полей соответсвующих информационным битам
и в матрицы ряды являются единичными.

Т.е наглядно достаточно легко определить синхорнизированны ли матрицы.
Но помимо синхроности нам нужна "правильность" синдрома:
рассмотрим синдромную матрицу

1010101
0110011
0001111  

повернем ее по часовой стрелки на 90 градусов :
битовое представление должно сооветсвовать номеру ряда:

001  1
010  2
011  3
100  4
101  5
011  6
111  7


Цитата(mes @  25.1.2009,  12:40 findReferencedText)
битовое представление должно соответствовать номеру ряда:

прямое соответсвие необязательно, но каждой строчке должен соответсвовать уникальный номер (не совпадующий с номерами в других рядах)
и в случае нелинейного  соответствия декодеру придется делать дополнительные действия для определения ошибочной позиции.

ava
mes | 25.01.2009, 15:24 #
вот сделал небольшую "библиотечку" (в стиле си с элементами с++) с тестовым примером , для пользования хеммингом

Добавлено позднее:

// unpack_bit.h
#pragma once
#include <iostream>


typedef unsigned char unpack_bit;


void char_to_bits8 (unsigned char c, unpack_bit* bits)
{
    for (int i=0; i<8; ++i)
      bits[i] = 1 & (c >> (7-i));

}
unsigned char bits8_to_char (unpack_bit* bits)
{
    unsigned char c = 0;
    for (int i=0; i<8; ++i)
      c |= bits[i] << (7-i);
    return c;
}

void print_bits  (const unpack_bit* bits, int count, const char *sep ="" ) //  sep - разделитель
{
    for (int i=0; i<count; ++i)
    std::cout <<int(bits[i]) << sep;
}




// hamming.h
#pragma once
#include "unpack_bit.h"

void hamming ( unpack_bit *bits, int bits_cnt, unpack_bit *ham, int ham_cnt, unpack_bit * M )
// bits - указатель на биты данных
// bits_cnt - кол-во элементов данных
// ham -  указатель на возвращаемую последовательность
// ham_bits - длина результа
// М - порождающая матрица [ham_cnt, bits_cnt] как линейная последовательность бит
{
    for( int i = 0; i < ham_cnt; ++i )
    {
      ham[i] = 0;
      for( int j = 0, ; j < bits_cnt; ++j )
        ham[i] ^= bits[j] & M[i*bits_cnt+j];
    }
}

int unhamming (unpack_bit *ham, int ham_cnt, unpack_bit *bits, int bits_cnt, unpack_bit * S, unpack_bit *I )
// bits - указатель на биты данных
// bits_cnt - кол-во элементов данных
// ham -  указатель на возвращаемую последовательность
// ham_bits - длина результа
// I - матрица [ bits_cnt, ham_cnt] получения информационных битов
// S - матрица [ ham_cnt-bits_cnt, ham_cnt] получения синдрома
{
// получаем синдром :
    unsigned s=0;
    int snd_cnt = ham_cnt-bits_cnt;
    for( int j = 0; j < snd_cnt; ++j )
       for( int i = 0; i < ham_cnt; ++i )
         s ^= (ham[i] & S[j*ham_cnt+i])<<j;


// если есть ошибка, востанавливаем порченный бит :
    if (s) ham[s-1]^=1;

// получаем данные :
    for( int j = 0, ; j < bits_cnt; ++j )
    {
       bits[j] = 0;
       for( int i = 0; i < ham_cnt; ++i )
         bits[j] ^= ham[i] & I[j*ham_cnt+i];
    }

    return s;
}


матрицы только для  кодирования 4х битового сообщения :

//hamming_matrix.h
#pragma once
#include "unpack_bit.h"


unpack_bit Hamming_M_7x4[7][4] = { { 1,1,0,1 }
                                 , { 1,0,1,1 }
                                 , { 1,0,0,0 }
                                 , { 0,1,1,1 }
                                 , { 0,1,0,0 }
                                 , { 0,0,1,0 }
                                 , { 0,0,0,1 }
                                 };

unpack_bit Hamming_S_3x7[3][7] =  { { 1,0,1,0,1,0,1 }
                                  , { 0,1,1,0,0,1,1 }
                                  , { 0,0,0,1,1,1,1 }
                                  };

unpack_bit Hamming_I_4x7[4][7] =  { { 0,0,1,0,0,0,0 }
                                  , { 0,0,0,0,1,0,0 }
                                  , { 0,0,0,0,0,1,0 }
                                  , { 0,0,0,0,0,0,1 }
                                  };




// hamming.cpp или main.cpp
#include <iostream>
#include "unpack_bit.h"
#include "hamming.h"
#include "hamming_matrix.h"


int main()
{

srand (1);

for (char q=0; q!='n' && q!='N'; std::cin >> q )
{
     std::cout <<std::endl;

// случайное число
     unpack_bit data[4]  = { 0 };
     for (int i=0; i<4; ++i)  data[i] = rand() & 1;
     std::cout << "data             : ";  print_bits (data, 4);   std::cout <<std::endl;

// хeмминг :
     unpack_bit ham[7]   = { 0 } ;
     hamming (data, 4, ham,7, Hamming_M_7x4[0]) ;
     std::cout << "ham              : ";  print_bits (ham, 7);    std::cout <<std::endl;

// портим случайный бит :
     int e = rand ()%8; if (e) ham[e-1]^=1;
     std::cout <<"error            : " <<e << std::endl;
     std::cout <<"ham (corrupted)  : ";  print_bits (ham, 7);    std::cout <<std::endl;

// анхeмминг:
     unpack_bit unham[4] = { 0 };
     int s = unhamming (ham,7, unham,4, Hamming_S_3x7[0],  Hamming_I_4x7[0]);
     std::cout << "syndrom          : " <<s << std::endl;
     std::cout << "ham (recovered)  : ";  print_bits (ham, 7);    std::cout <<std::endl;
     std::cout << "unham            : ";  print_bits (unham, 4);  std::cout <<std::endl;


     std::cout << "repeat  (y/n)? ";
}
}

Зарегистрируйтесь или войдите, чтобы написать.
Фирма дня
Вы также можете добавить свою фирму в каталог IT-фирм, и публиковать статьи, новости, вакансии и другую информацию от имени фирмы.
Подробнее
Участники
advanced
Отправить