Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Для новичков > кодирование

Автор: Vicipi 18.1.2009, 10:31

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

Автор: mes 18.1.2009, 18:29

может поможет : http://www.intuit.ru/department/calculate/infotheory/9/2.html

Автор: Vicipi 18.1.2009, 22:50

информация полезная, но не помогла...

Автор: Kallikanzarid 19.1.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.      */ }

Автор: GoldFinch 19.1.2009, 07:36

разве такое не решается таблицей из 16 элементов7

Автор: Vicipi 19.1.2009, 20:02

Код values[i] = x1 * 2^4 + x2.   Что это?

Автор: mes 19.1.2009, 20:10

Цитата(Vicipi @  19.1.2009,  19:02 ) Что это?   Это  "^"  ?  исключающее_или (xor) поиск поможет Цитата(Vicipi @  18.1.2009,  09:31 ) дана матрица А= матрица, имхо, неправильная, контрольные ряды должны распологаться по степеням двойки то есть ряды 1,2,4 а у Вас 1,2,3. Цитата(GoldFinch @  19.1.2009,  06:36 ) разве такое не решается таблицей из 16 элементов7  решается для кодирования. Но таблица не позволяет узнать в каком ряду ошибка.

Автор: Vicipi 19.1.2009, 20:26

Цитата(Vicipi @  19.1.2009,  20:02 ) Что это?  в смысле что за формула такая, что за x1 и x2, для чего она?

Автор: mes 19.1.2009, 22:37

Цитата(Vicipi @  19.1.2009,  19:26 ) в смысле что за формула такая, что за x1 и x2, для чего она?  а откуда она появилась то ? в приведенном коде не нашел.

Автор: Vicipi 20.1.2009, 22:01

Цитата(Kallikanzarid @  19.1.2009,  06:09 ) Тут, видимо, синопсис такой: char values[n] - массив n векторов, values[i] = x1 * 2^4 + x2. до кода.

Автор: mes 24.1.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;

Автор: mes 24.1.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];

Автор: mes 24.1.2009, 01:06

Как уже было сказано выше, матрица нужна чтоб не зависить от порядка рассположения битов в последовательностях и способа расчета контрольной суммы. Все три матрицы должны быть синхронизированны относительной общей схемы кодирования. Расположение информационых и контрольных бит в последовательности хемминга тоже не случайно, оно выбрано таким образом, чтоб по ошибке в контрольной сумме , можно было узнать номер испорченного бита ну и напоследок тут подробно изложено по теме со схемами : http://lib.aanet.ru/pdf/kafedra22/d2.pdf

Автор: mes 24.1.2009, 01:35

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

Автор: mes 25.1.2009, 13:40

Цитата("Vicipi(pm)") а как определить правильная матрица или нет? протестить  Во первых: Цитата(mes @  24.1.2009,  00:06 ) Все три матрицы должны быть синхронизированны относительной общей схемы кодирования. Во вторых: Цитата(mes @  23.1.2009,  23:45 ) матрица нужна , чтоб автоматизировать процесс ,  в ней выражено какие биты надо использовать для операций. Порождающая матрица представляет формулу, которая кодируют контрольные биты так, чтоб ошибка четности, показывала испорченого номер бита Также она показывает в каком месте будет располагаться биты сообщения. для вышеупомянотого 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 ) битовое представление должно соответствовать номеру ряда: прямое соответсвие необязательно, но каждой строчке должен соответсвовать уникальный номер (не совпадующий с номерами в других рядах) и в случае нелинейного  соответствия декодеру придется делать дополнительные действия для определения ошибочной позиции.

Автор: mes 25.1.2009, 15:24

вот сделал небольшую "библиотечку" (в стиле си с элементами с++) с тестовым примером , для пользования хеммингом Добавлено @ 15:28 Код // 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)? ";  } }

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)