[repstosw 18]

Не могу понять, как определяется корректирующая способность BCH кодов.   Тоесть, сколько максимально код может исправить ошибок в блоке.

С Ридом-Соломоном всё ясно:  есть блок определённой длины, к нему дописываются проверочные символы.  Максимально может исправить половину длины проверочных символов.  А с BCH как посчитать?  И что собственно BCH исправляет: одиночные биты незавивимо от байт или как?

[Lotos 4]

Смотрите графу "t" в таблицах стр.368-372 в книге "Кодирование с исправлением ошибок в системах цифровой связи"  Кларк Дж., Кейн Дж. // Пер. с англ. С.И.Гельфанда под ред. Б.С. Цыбакова – М.: Радио и связь, 1987. 392 с. 

Приложение А. Порождающие многочлены для кодов БЧХ

[repstosw 18]

6 hours ago, Lotos said:

Смотрите графу "t" в таблицах стр.368-372 в книге "Кодирование с исправлением ошибок в системах цифровой связи"  Кларк Дж., Кейн Дж. // Пер. с англ. С.И.Гельфанда под ред. Б.С. Цыбакова – М.: Радио и связь, 1987. 392 с. 

Приложение А. Порождающие многочлены для кодов БЧХ

Посмотрел графу "t" в таблицах.  Что мне это должно дать?

 

Допустим у меня есть рабочая реализация кодека Рида-Соломона, оптимизированная для укороченных кодов. GF 2^16. Общая длина 65535 символов (по 16 бит).  Использую укороченный код с оптимизированным алгоритмом: 6000 символов,  из них 600 символов - проверочные.  Такой код исправит максимум 300 символов в любом месте - на позициях 0...5999.

А с BCH как?  Как найти равновеликий код BCH, который мог бы тягаться с укороченным RS (6000,5400) ?

И ещё, на счёт трудоёмкости вычислений.  Использую оптимизированную версию кодека RS  от Phil Karn.  На ARM Cortex-A7 1200 МГц - кодирование занимает 35 FPS, декодирование 14 FPS. Это когда число ошибок максимально - и оно исправляется (300 из 6000).

Что будет с производительностью BCH?  Он более трудозатратный по вычислениям или нет?

Есть ли способ переложить код на NEON и распараллелить вычисления?  Основная проблема - табличные доступы к массивам Alpha_To и Index_Of - слишком хаотичные выборки, засоряющие кеш.

https://github.com/quiet/libfec/blob/master/decode_rs.c

С параллельной оптимизацией на SIMD видел у RS Leopard, но там декодирование по известным позициям ошибок(стирания), что мне не подходит:

https://github.com/catid/leopard

Итак, 2 вопроса:

1) Мощность BCH кодов по сравнению с RS

2) Оптимизированные версии кодеков BCH и или RS под ARM NEON...

Изменено 30 октября, 2023 пользователем repstosw

[thermit 1]

рс - тоже бчх. Алгоритм декодирования одинаков.

Про таблицы - это наиболее простой способ вычислений в GF(q).  Параллелить там ничего не возможно.

[andyp 9]

On 10/29/2023 at 10:54 AM, repstosw said:

Не могу понять, как определяется корректирующая способность BCH кодов.   Тоесть, сколько максимально код может исправить ошибок в блоке.

При выборе БЧХ исправляющая способность  - входной параметр. Сколько надо, чтобы код гарантированно исправлял. А скорость кодирования будет такая, какая получится. Код этот бинарный, исправляет битовые ошибки. Например BCH(255,131,37) исправляет 37 битовых ошибок при скорости кодирования 131/255

Для количества информационных бит существует следующая граница снизу  k >= n - m*t,

n = 2^m - 1 - длина блока

t  - требуемая исправляющая способность

k - количество информационных бит

Изменено 30 октября, 2023 пользователем andyp

[repstosw 18]

5 hours ago, thermit said:

Про таблицы - это наиболее простой способ вычислений в GF(q).  Параллелить там ничего не возможно.

Основной тормоз в таких алгоритмах - таблицы больших размеров, из которых выборки идут хаотично. Слишком сильно страдает кеш данных.

Возможно ли уменьшить размер этих таблиц, перейдя к преобразованиям от GF(2^16) к GF((2^8) ^2) ?    Вроде видел кое-какие проблески, но не исчерпывающе:

https://web.eecs.utk.edu/~jplank/plank/papers/UT-CS-13-717.pdf

Изменено 30 октября, 2023 пользователем repstosw

[thermit 1]

7 часов назад, repstosw сказал:

Основной тормоз в таких алгоритмах - таблицы больших размеров, из которых выборки идут хаотично. Слишком сильно страдает кеш данных.

Возможно ли уменьшить размер этих таблиц, перейдя к преобразованиям от GF(2^16) к GF((2^8) ^2) ?    Вроде видел кое-какие проблески, но не исчерпывающе:

https://web.eecs.utk.edu/~jplank/plank/papers/UT-CS-13-717.pdf

 

Нет.

[repstosw 18]

10 hours ago, thermit said:

Нет.

Проверил. Уменьшил размер таблиц в 2 раза, за счёт того что нечётные элементы - находились выборкой чётных элементов из таблицы + 1 итерация сдвигов с полиномом. К сожалению, прибавки к скорости не дало.  Потому что вычислизмы отняли тот же ресурс, что и обращения к таблице.

 

А если взять  Fermat-реализацию RS?  Так называвемый RS-кодек в GF(2^16 + 1) : https://github.com/fdidier/fermat-reed-solomon

Хорош тем, что общий блок уже 65536 элементов, и процедура взятия остатка от деления на 65536 - это простейшее обнуление бит, старше 15-го,  что намного быстрее, чем взятие остатка от деления на 65535.   А взятие остатка - очень рутинная функция - она во всех циклах кодека присутствует - особенно во внутренних.

 

P.S. И да, ... что это за поле такое GF(2^16 + 1) ? 🙂  Обычно на 1 меньше.

Изменено 31 октября, 2023 пользователем repstosw

[des00 25]

28 minutes ago, repstosw said:

Хорош тем, что общий блок уже 65536 элементов, и процедура взятия остатка от деления на 65536 - это простейшее обнуление бит, старше 15-го,  что намного быстрее, чем взятие остатка от деления на 65535.   А взятие остатка - очень рутинная функция - она во всех циклах кодека присутствует - особенно во внутренних.

так а там же оно аппроксимируется через одноранговое вычитание. ЕМНП все случаи этого остатка связаны с тем что делимое меньше двух делителей. 

[repstosw 18]

1 hour ago, des00 said:

так а там же оно аппроксимируется через одноранговое вычитание. ЕМНП все случаи этого остатка связаны с тем что делимое меньше двух делителей. 

Вот здесь: https://github.com/quiet/libfec/blob/master/decode_rs.c   

остаток от деления на 65535.   Нету однорангового вычитания.

Собственно,  как сложить два числа с остатком от деления на 65535 ?

тоесть  (a+b)%65535 ?

не прибегая к вычислению остатка от деления (в т.ч. и самого деления)

[des00 25]

5 hours ago, repstosw said:

Собственно,  как сложить два числа с остатком от деления на 65535 ?

тоесть  (a+b)%65535 ?

не прибегая к вычислению остатка от деления (в т.ч. и самого деления)

да вроде всегда так делали, вычитанием если надо.

c = a + b;

rslt = (c >= 65535) ? (c - 65535) : c

это в случае однорангового, когда с < 2*65535. А сложение двух элементов полей Галуа у вас как раз и замыкается в этом круге. Не знаю есть ли у вашего проца опции условного исполнения команд, но может быть это будет проще чем делить?

UPD. Посмотрел выложенный код, чтобы применить этот подход вам надо полностью переписывать все что выложено. Например

[MODNN(INDEX_OF[s[i]] + (FCR+i)*PRIM)];

i тут бежит с 0 до NROOTS, и естественно здесь будет не одноранговое деление. Но, например тут не обязательно умножать да еще и каждый блок, т.к. мы работаем в поле, можно вычислить константы уже по модулю MODNN((FCR+i)*PRIM),  обеспечив уже попадание этого значения в кольцо 0..65534, а потом, прибавляя элемент INDEX_OF[bla bla bla], вы как раз и получите то что можно делить одним вычитанием. Но это надо полностью переписывать этот декодер и тогда он потеряет свою универсальность, выродившись в собственную кастомную разработку.

[sasamy 9]

On 10/30/2023 at 4:05 AM, repstosw said:

2) Оптимизированные версии кодеков BCH и или RS под ARM NEON

эту не смотрели ?

https://github.com/HAMNET-Access-Protocol/libfec

[repstosw 18]

4 hours ago, sasamy said:

эту не смотрели ?

https://github.com/HAMNET-Access-Protocol/libfec

Смотрел.  Всё теже самые тормоза, нуждающиеся в оптимизации.  Конкретно меня интересует RS GF(2^16):

https://github.com/HAMNET-Access-Protocol/libfec/blob/master/decode_rs.h#L218

Поиск Ченя не оптимизирован: цикл от 1 до NN - тоесть на всю длину блока 65535 символов.  На моём ПК это даёт 12 - 15  FPS всего.

Нужно оптимизировать, к примеру полезная длина  2976 символов + проверочные (600-16) символов:

//1 ------------------------------------------

 for(j=deg_lambda;j>0;j--)if(reg[j]!=A0)reg[j]=MODNN(reg[j]+(j*((NN-1)+1-(2976+600-16))));

 k=(NN-1)-(2976+600-16);

//2 ------------------------------------------
  for(i=2976+600-16-1;i>=0;i--)
  {
   q = 1; /* lambda[0] is always 0 */

   for(j=deg_lambda;j>0;j--)
   {
    if(reg[j]!=A0)
    {
     reg[j]=MODNN(reg[j]+j);
     q^=ALPHA_TO[reg[j]];
    }
   }
  
   k++;

   if(q!=0)continue; /* Not a root */

   /* store root (index-form) and error location number */

   root[count]=NN-i;
   loc[count]=k;

   /* If we've already found max possible roots,
    * abort the search to save time
   */
   if(++count==deg_lambda)break;
  }

 

Плюс элемент массивов должен быть short int, а не Int.  Это даёт возможность в 2 раза меньше загружать кеш.  Так как размерность символа как раз укладывается в short int, нет надобности забивать кеш ненужными нулями.

 

С этими двумя приёмами FPS на ПК вырос до 68 - 70.  При условии, если  декодируется пакет с максимально допустимым числом ошибок - (600-16)/2 символов.

 

Бенчмарк в спойлере:

Spoiler

/* Test the Reed-Solomon codecs
 * for various block sizes and with random data and random error patterns
 *
 * Copyright 2002 Phil Karn, KA9Q
 * May be used under the terms of the GNU Lesser General Public License (LGPL)
 */

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <time.h>
#include "fec.h"

#define random rand
#define srandom srand

struct etab {
  int symsize;
  int genpoly;
  int fcs;
  int prim;
  int nroots;
  int ntrials;
} Tab[] = {
  {9, 0x211,   1,   1, 32, 10 },
  {10,0x409,   1,   1, 32, 10 },
  {11,0x805,   1,   1, 32, 10 },
  {12,0x1053,  1,   1, 32, 5 },
  {13,0x201b,  1,   1, 32, 2 },
  {14,0x4443,  1,   1, 32, 1 },
  {15,0x8003,  1,   1, 32, 1 },

  { 16,0x1100b, 1,   1,   /*32*/ (600-16),     1 }, //!!!
// sym genpoly fcs prim nroots ntrials
  {0, 0, 0, 0, 0},
};

int exercise_int(struct etab *e);

int main(void)
{
  int i=7;

  srandom(time(NULL));

  int nn,kk;

  nn = (1<<Tab[i].symsize) - 1;
  kk = nn - Tab[i].nroots;

  exercise_int(&Tab[i]);
}

#define u16 unsigned short

static __inline__ unsigned long long rdtsc(void)
{
    unsigned hi, lo;
    __asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
    return ( (unsigned long long)lo)|( ((unsigned long long)hi)<<32 );
}

int exercise_int(struct etab *e)
{
  int nn = (1<<e->symsize) - 1;
  data_t block[nn],tblock[nn];
  int i;
  int errors;
  int derrors,kk;
  int errval,errloc;
  int erasures;
  int decoder_errors = 0;
  void *rs;

  /* Compute code parameters */
  kk = nn - e->nroots;

  #define K   2976
  #define E   e->nroots
  #define PAD (nn-e->nroots-K)

  printf("start!\n");

  rs=init_rs_int(e->symsize,e->genpoly,e->fcs,e->prim,e->nroots,PAD);

  if(rs==NULL)
  {
   printf("init_rs_int failed!\n");
   return -1;
  }
  else printf("inited!\n");

  unsigned long long t=0;

  Loop:

  memset(block,0,sizeof(block));

  /* Load block with random data and encode */
  for(i=0;i<K;i++)block[i]=((u16)random())&nn;

  memcpy(tblock,block,sizeof(block));

  t=rdtsc();
  encode_rs_int(rs,block,&block[K]);
  t=rdtsc()-t;
  printf("Encode: %0.1lf FPS   ",(double)3000000000ULL/(double)t); //"%llu\n"


  /* Make temp copy, seed with errors */
  memcpy(tblock,block,sizeof(block));

  for(int i=0;i<(E/2)+0;i++)tblock[(((u16)rand())%(K+E))]=(u16)rand();

  /* Decode the errored block */
  t=rdtsc();
  derrors=decode_rs_int(rs,tblock,NULL,0);
  t=rdtsc()-t;
  printf("Decode: %0.1lf FPS\n",(double)3000000000ULL/(double)t); //"%llu\n"

  if(memcmp(tblock,block,sizeof(tblock))!=0)
  {
   printf("Decode Error!\n");
   while(1);
  }
//  else printf("All OK!\n");

  goto Loop;

  free_rs_int(rs);

  return 0;
}

 

Изменено 31 октября, 2023 пользователем repstosw

[thermit 1]

9 часов назад, repstosw сказал:

Проверил. Уменьшил размер таблиц в 2 раза, за счёт того что нечётные элементы - находились выборкой чётных элементов из таблицы + 1 итерация сдвигов с полиномом. К сожалению, прибавки к скорости не дало.  Потому что вычислизмы отняли тот же ресурс, что и обращения к таблице.

 

А если взять  Fermat-реализацию RS?  Так называвемый RS-кодек в GF(2^16 + 1) : https://github.com/fdidier/fermat-reed-solomon

Хорош тем, что общий блок уже 65536 элементов, и процедура взятия остатка от деления на 65536 - это простейшее обнуление бит, старше 15-го,  что намного быстрее, чем взятие остатка от деления на 65535.   А взятие остатка - очень рутинная функция - она во всех циклах кодека присутствует - особенно во внутренних.

 

P.S. И да, ... что это за поле такое GF(2^16 + 1) ? 🙂  Обычно на 1 меньше.

 

Да эти вычисления  в принципе не поддаются оптимизации. Что есть - то есть. gf(q) q выбирается либо простым, либо степень простого. Обычно. Тогда есть примитивный элемент, степени которого пробегают все множество чисел <q не равные 0. Тогда это примитивный бчх. Но бывают и не примитивные бчх. 65537 - простое число.

[repstosw 18]

On 11/1/2023 at 1:44 AM, thermit said:

Но бывают и не примитивные бчх. 65537 - простое число.

Данный полином не удвовлетворил кодек Рида -Соломона.

Вот эти удовлетворяют (записаны в 8-ричной системе счисления, для GF 2^16):

       210013,  234313,  233303,  307107,  307527,  306357,
       201735,  272201,  242413,  270155,  302157,  210205,
       305667,  236107

 

On 10/31/2023 at 6:53 PM, des00 said:

да вроде всегда так делали, вычитанием если надо.

c = a + b;

rslt = (c >= 65535) ? (c - 65535) : c

Почему-то этот вариант работает медленее (на ARM Cortex-A7), чем вот этот вариант:

unsigned int modnn(unsigned int x)
{
 while(x>=65535)
 {
  x-=65535;
  x=(x>>16)+(x&65535);
 }
 return x;
}

 

В чём фокус? Функция попала целиком в кеш?  Или аппаратное выполнение по условию?