repstosw 18 29 октября, 2023 Опубликовано 29 октября, 2023 · Жалоба Не могу понять, как определяется корректирующая способность BCH кодов. Тоесть, сколько максимально код может исправить ошибок в блоке. С Ридом-Соломоном всё ясно: есть блок определённой длины, к нему дописываются проверочные символы. Максимально может исправить половину длины проверочных символов. А с BCH как посчитать? И что собственно BCH исправляет: одиночные биты незавивимо от байт или как? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Lotos 4 29 октября, 2023 Опубликовано 29 октября, 2023 · Жалоба Смотрите графу "t" в таблицах стр.368-372 в книге "Кодирование с исправлением ошибок в системах цифровой связи" Кларк Дж., Кейн Дж. // Пер. с англ. С.И.Гельфанда под ред. Б.С. Цыбакова – М.: Радио и связь, 1987. 392 с. Приложение А. Порождающие многочлены для кодов БЧХ Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
repstosw 18 30 октября, 2023 Опубликовано 30 октября, 2023 (изменено) · Жалоба 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 30 октября, 2023 Опубликовано 30 октября, 2023 · Жалоба рс - тоже бчх. Алгоритм декодирования одинаков. Про таблицы - это наиболее простой способ вычислений в GF(q). Параллелить там ничего не возможно. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
andyp 10 30 октября, 2023 Опубликовано 30 октября, 2023 (изменено) · Жалоба 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 1 Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
repstosw 18 30 октября, 2023 Опубликовано 30 октября, 2023 (изменено) · Жалоба 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 30 октября, 2023 Опубликовано 30 октября, 2023 · Жалоба 7 часов назад, repstosw сказал: Основной тормоз в таких алгоритмах - таблицы больших размеров, из которых выборки идут хаотично. Слишком сильно страдает кеш данных. Возможно ли уменьшить размер этих таблиц, перейдя к преобразованиям от GF(2^16) к GF((2^8) ^2) ? Вроде видел кое-какие проблески, но не исчерпывающе: https://web.eecs.utk.edu/~jplank/plank/papers/UT-CS-13-717.pdf Нет. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
repstosw 18 31 октября, 2023 Опубликовано 31 октября, 2023 (изменено) · Жалоба 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 31 октября, 2023 Опубликовано 31 октября, 2023 · Жалоба 28 minutes ago, repstosw said: Хорош тем, что общий блок уже 65536 элементов, и процедура взятия остатка от деления на 65536 - это простейшее обнуление бит, старше 15-го, что намного быстрее, чем взятие остатка от деления на 65535. А взятие остатка - очень рутинная функция - она во всех циклах кодека присутствует - особенно во внутренних. так а там же оно аппроксимируется через одноранговое вычитание. ЕМНП все случаи этого остатка связаны с тем что делимое меньше двух делителей. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
repstosw 18 31 октября, 2023 Опубликовано 31 октября, 2023 · Жалоба 1 hour ago, des00 said: так а там же оно аппроксимируется через одноранговое вычитание. ЕМНП все случаи этого остатка связаны с тем что делимое меньше двух делителей. Вот здесь: https://github.com/quiet/libfec/blob/master/decode_rs.c остаток от деления на 65535. Нету однорангового вычитания. Собственно, как сложить два числа с остатком от деления на 65535 ? тоесть (a+b)%65535 ? не прибегая к вычислению остатка от деления (в т.ч. и самого деления) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
des00 25 31 октября, 2023 Опубликовано 31 октября, 2023 · Жалоба 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 0 31 октября, 2023 Опубликовано 31 октября, 2023 · Жалоба On 10/30/2023 at 4:05 AM, repstosw said: 2) Оптимизированные версии кодеков BCH и или RS под ARM NEON эту не смотрели ? https://github.com/HAMNET-Access-Protocol/libfec Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
repstosw 18 31 октября, 2023 Опубликовано 31 октября, 2023 (изменено) · Жалоба 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 31 октября, 2023 Опубликовано 31 октября, 2023 · Жалоба 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 2 ноября, 2023 Опубликовано 2 ноября, 2023 · Жалоба 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; } В чём фокус? Функция попала целиком в кеш? Или аппаратное выполнение по условию? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться