fork download
copy 
  1. #include <stdio.h>
  2.  
  3. #include <math.h>		// для time
  4.  
  5.  
  6. static const unsigned int golay_encode_matrix[12] = 
  7. {
  8.  0xC75, 0x49F, 0xD4B, 0x6E3, 0x9B3, 0xB66, 0xECC, 0x1ED, 0x3DA, 0x7B4, 0xB1D, 0xE3A,
  9. };
  10.  
  11. static const unsigned int golay_decode_matrix[12] = 
  12. {
  13.  0x49F, 0x93E, 0x6E3, 0xDC6, 0xF13, 0xAB9, 0x1ED, 0x3DA, 0x7B4, 0xF68, 0xA4F, 0xC75,
  14. };
  15.  
  16. /// Функция для вычисления веса Хэмминга 12-разрядного целого числа
  17. static unsigned int weight12(unsigned int vector)
  18. {
  19.     unsigned int w=0;
  20.     for(char i=0; i<12; i++ )
  21.       {
  22. 		if( vector & 1 )    w++;
  23. 	   	vector>>=1;
  24.       }
  25.     return w;
  26. }
  27.  
  28. /// возвращает Golay-код данного 12-битного слова
  29. unsigned int golay_coding(unsigned int w)
  30. {
  31.     unsigned int out=0;
  32.  
  33.     for(char i = 0; i<12; i++ ) 
  34.     {
  35. 		if( w & 1 )   out ^= golay_encode_matrix[i];
  36. 		w>>=1;
  37.     }
  38.     return out;
  39. }
  40.  
  41.  
  42.  
  43. /// возвращает декодированный Golay-код данного 12-битного слова 
  44. unsigned int golay_decoding(unsigned int w)
  45. {
  46.     unsigned int out=0;
  47.  
  48.     for(char i = 0; i<12; i++ ) 
  49.     {
  50. 		if( w & 1 )    out ^= golay_decode_matrix[i];
  51. 		w>>=1;
  52.     }
  53.     return out;
  54. }
  55.  
  56.  
  57. /// Вернуть маску ошибочных битов в received_data или 0xFFFF если ошибок слишком много
  58.  
  59. unsigned int golay_errors(unsigned int received_data,unsigned int received_parity)//(unsigned long codeword)
  60. {
  61.     unsigned int syndrome;
  62.     unsigned int w,i;
  63.     unsigned int inv_syndrome = 0;
  64.  
  65. //    received_parity = (unsigned int)(codeword>>12);
  66. //    received_data   = (unsigned int)codeword & 0xfff;
  67.  
  68.     /* We use the C notation ^ for XOR to represent addition modulo 2.
  69.      *
  70.      * Model the received codeword (r) as the transmitted codeword (u)
  71.      * plus an error vector (e).
  72.      *
  73.      *   r = e ^ u
  74.      *
  75.      * Then we calculate a syndrome (s):
  76.      *
  77.      *   s = r * H, where H = [ P   ], where I12 is the identity matrix
  78.      *                        [ I12 ]
  79.      *
  80.      * (In other words, we calculate the parity check for the received
  81.      * data bits, and add them to the received parity bits)
  82.      */
  83.  
  84.     syndrome = received_parity ^ (golay_coding(received_data));
  85.     w = weight12(syndrome);
  86.  
  87. /*
  88. Свойства кода Галея таковы, что расстояние Хемминга (то есть, минимальное расстояние между кодовыми словами) 8;
  89. что означает, что один бит ошибки в битах данных, вызовет 7 ошибок в битах четности.
  90.  
  91.  В частности, если мы находим, 3 или меньше ошибок в битах четности, либо:
  92.   - Нет ошибки в битах данных, или
  93.   - Есть по крайней мере 5 ошибок в битах данных, мы надеемся, что в первом случае (мы не исповедуем иметь дело с последним). 
  94. */
  95.     if( w <= 3 ) 
  96. 	  {
  97. //		return ((long) syndrome)<<12;
  98. 		return 0;		// в данных ошибок нет (или больше 5)
  99.       }
  100.  
  101. /*
  102.  the next thing to try is one error in the data bits.
  103.  we try each bit in turn and see if an error in that bit would have given
  104.  us anything like the parity bits we got. At this point, we tolerate two
  105.  errors in the parity bits, but three or more errors would give a total
  106.  error weight of 4 or more, which means it's actually uncorrectable or
  107.  closer to another codeword. 
  108. следующая вещь, чтобы попытаться это одна ошибка в биты данных. 
  109. мы стараемся каждый бит, в свою очередь, и увидеть, если ошибка в том,
  110.  что бит дал бы нам что-нибудь, как биты четности, которые мы получили.
  111. На данный момент, мы терпим две ошибки в битах четности, 
  112. но три или больше ошибок будет давать общую массу ошибок 4 или более,
  113. что означает, что на самом деле неисправимая или ближе к другому кодовому слову.
  114. */
  115.  
  116.     for( i = 0; i<12; i++ ) 
  117. 	  {
  118. 		unsigned int error = 1<<i;
  119. 		unsigned int coding_error = golay_encode_matrix[i];
  120. 		if( weight12(syndrome^coding_error) <= 2 ) 
  121. 		  {
  122. 			//return (long)((((unsigned long)(syndrome^coding_error))<<12) | (unsigned long)error) ;
  123. 			return error ;		// возвращаю только ошибку в данных
  124. 		  }
  125.       }
  126.  
  127. /*
  128.  okay then, let's see whether the parity bits are error free, and all the
  129.  errors are in the data bits. model this as follows:
  130. Хорошо, давайте посмотрим, биты четности, являются ли ошибок, и все ошибки в битах данных. 
  131. эта модель выглядит следующим образом:
  132.  * [r | pr] = [u | pu] + [e | 0]
  133.  *
  134.  * pr = pu
  135.  * pu = H * u => u = H' * pu = H' * pr , where H' is inverse of H
  136.  *
  137.  * we already have s = H*r + pr, so pr = s - H*r = s ^ H*r
  138.  * e = u ^ r
  139.  *   = (H' * ( s ^ H*r )) ^ r
  140.  *   = H'*s ^ r ^ r
  141.  *   = H'*s
  142.  *
  143.  * Опять же, мы принимаем до трех ошибочных битов...
  144.  */
  145.  
  146.     inv_syndrome = golay_decoding(syndrome);
  147.     w = weight12(inv_syndrome);
  148.     if( w <=3 ) {
  149. 	return inv_syndrome;
  150.     }
  151.  
  152. /*
  153.  Final shot: try with 2 errors in the data bits, and 1 in the parity
  154.  bits; as before we try each of the bits in the parity in turn 
  155. Заключительный выстрел: попробуйте 2 ошибки в битах данных, и 1 в биты четности;
  156. как и прежде мы стараемся каждый из битов в четности в свою очередь,
  157. */
  158.     for( i = 0; i<12; i++ ) 
  159. 	  {
  160. 		unsigned int error = 1<<i;
  161. 		unsigned int coding_error = golay_decode_matrix[i];
  162. 		if( weight12(inv_syndrome^coding_error) <= 2 ) 
  163. 		  {
  164. //			unsigned long error_word = ((unsigned long)(inv_syndrome^coding_error)) | ((unsigned long)error)<<12;
  165. //			return (long)error_word;
  166. 			unsigned int error_word = inv_syndrome^coding_error;
  167. 			return error_word;
  168. 		  }
  169.       }
  170.  
  171.     /* uncorrectable error */
  172.     return 0xFFFF;
  173. }
  174.  
  175.  
  176. ///  возвращает  12-битный Golay-паритет от слова данных
  177. unsigned int golay_encode(unsigned int w)
  178. {
  179.     return golay_coding(w);
  180. }
  181.  
  182.  
  183. /* decode a received codeword. Up to 3 errors are corrected for; 4
  184.    errors are detected as uncorrectable (return 0xFFFF); 5 or more errors
  185.    cause an incorrect correction.
  186. */
  187. unsigned int golay_decode(unsigned int data,unsigned int parity)
  188. {
  189.     unsigned int data_errors= golay_errors(data,parity);
  190.  
  191.     if( data_errors == 0xFFFF )
  192. 	return 0xFFFF;
  193. //    data_errors = (unsigned int)errors & 0xfff;
  194.     return (data ^ data_errors);
  195. }
  196.  
  197.  
  198. int main(void)
  199.  {		// test 
  200.  
  201.    unsigned int Codeword;          		// Codeword composed of 12-bit info and 12-bit parity 
  202.    unsigned int Paritet;		// Received vector in two halfs of 12 bits each 
  203.  
  204.    unsigned int Syndrome;             
  205.    int modified_syndrome;             
  206.    int Codeword_out;      // Расчетное кодовое слово 
  207.  
  208.    long seed;
  209.    ///
  210.    time(&seed);
  211.    srandom(seed);
  212.    Codeword = random()&0xfff;
  213.    printf("c =%03X\n", Codeword);
  214.  
  215.  
  216.    ///
  217. 	Paritet=golay_encode(Codeword);
  218. 	printf("t =%03X%03X\n", Codeword,Paritet);
  219.  
  220. 	///
  221. unsigned int	error_Codeword=(random()&0x030);
  222. unsigned int	error_Paritet=(random()&0x101);
  223.  
  224. 	printf("e =%03X%03X, w(e) = %d\n", error_Codeword,error_Paritet, weight12(error_Codeword)+weight12(error_Paritet));
  225.  
  226. 	///
  227. 	Codeword^=error_Codeword;
  228. 	Paritet^=error_Paritet;
  229. 	printf("r =%03X%03X\n",Codeword,Paritet);
  230.  
  231. 	///
  232.  
  233.  
  234. 	printf("E =%03X\n", golay_errors(Codeword,Paritet));
  235.  
  236. 	printf("c =%03X\n", golay_decode(Codeword,Paritet));
  237.  
  238. return 0;	
  239. }
  240.  
Success #stdin #stdout 0s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
c =E0A
t =E0A0EF
e =010001, w(e) = 2
r =E1A0EE
E =010
c =E0A
https://ideone.com/piAORG
language:
C (gcc 8.3)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!