Востановить небольшое количество потерянных пакетов

Оказывается CRC на позволит исправлять k ошибок, потому что если составлять произвольные матрицы из векторов остатков, то матрица может оказаться вырожденной и найти обратную к ней мы не сможем. Видимо придётся всё же разбирать коды Рида-Соломона.

 

По себе знаю, очень трудно преодолеть психологический барьер и перейти от одиночных бит к более широким полям галуа. Если построить таблицу умножения байт-на-байт, или менее требовательную к памяти байтовую таблицу логарифмов-экспонент, то можно будет исправлять любую комбинацию ошибок кратности до 256.

 

Black_mirror
А чем вам это всё поможет, если пакет тупо не пришёл? Существующие интернет сети не реалтайм.

 

persicum
Мне не особо хочется применять коды Рида-Соломона, потому что для исправления ошибки в одном символе требуется два дополнительных. Но что-то мне подсказывает что поскольку позиции ошибок известны, то по идее должно хватать одного дополнительного символа.

 

Booster
Информационные блоки и блоки контрольного кода можно расположить в разных пакетах, в этом случае потеря одного пакета приводит к потере всего одного блока, и поэтому его можно будет восстановить. А если выбрать хороший код, то можно будет восстановить и более одного блока. Естественно что и контрольных блоков добавится.

 

Booster

..или несколько пакетов подряд не пришло.

Black_mirror

проблема ведь не в потере битов, а в потере пакетов.

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

 

Единственно рабочее решение это буферизация хотя-бы на секунду или более.

 

Ну можно скорость передачи снизить - 3/500 это очень малая величина. Возможно простейшее сжатие поможет оставить скорость передачи (плотность данных) на прежнем уровне.

 

* "простейшее сжатие" - тупое схлопывание повторяющихся данных/или использование неиспользуемых разрядов - например идет гистограмма с 256 каналов и где-то там пик ~20000. Но во многих каналах данные почти никогда не могут быть >255.

 

PSR1257
В общем случае только буферизация, так как шлюзы тоже буферизуют.

 

сжимать можно и если выборки делать не по времени, а например, по скорости изменения. но это от характера данных зависит

 

qqwe
На счёт нескольких пакетов подряд. Если мы возьмём любой CRC, то он позволяет востановить 2 бита, при условии что длина сообщения с присоединённым CRC меньше чем длина периода генерируемого данным полиномом. Происходит так потому, что все остатки у нас различные, и при сложении двух из них мы не получим нуль, нам нужно добавить как минимум еще один. Можно взять CRC который позволит востановить 3 ошибки, выбирается он относительно просто, его полином содержит чётное число единичных коэффициентов, поэтому если начать генерацию с остатка с нечётным числом единиц, то будем получать остатки только с нечётным числом единиц. Если использовать только такие остатки, то их понадобится как минимум 4 штуки чтобы получить 0, то есть любые 3 неизвестные бита востанавливатются однозначным образом. Точно знаю, что существует полином 16й степени с периодом 1285, для которого нужно взять минимум 5 остатков чтобы получился 0, то есть он позволяет востанавливать до 4х ошибок. Это если расматривать задачу исправления ошибок в известных позициях.

Booster
PSR1257
"Буферизация", "снизить скорость", "использовать сжатие" - это всё слишком частные решения.

 

ну разумеется так оно и есть! Берешь свои пакеты и кодируешь байтовые срезы раз за разом, проверочные байты складываешь в новые пакеты.
Алгоритм:

1) строишь поле галуа GF(2^8) , сложение и вычитание это привычный XOR, также организуешь умножение и поиск обратного элемента.

2) для матрицы 100х10 задаешься i=0..9, j=0..99,
вычисляешь матрицу как F(i,j)=1/((100+i) XOR j)

3) берешь байтовые срезы своих 100 пакетов и умножая их на матрицу получаешь 10 проверочных пакетов

4) теперь достаточно получить любые 100 пакетов из 110 и обычными методами линейной алгебры вычислить из них 100 пакетов с данными.

 

Black_mirror
>"Буферизация", "снизить скорость", "использовать сжатие" - это всё слишком частные решения.
Для Вас частные, для всех общие.

 

persicum
Правильно ли я понимаю, что любые 10 строк из матрицы F являются линейно независимые? При данном способе построения F это будет выполняться только пока сумма числа элементов в строке и столбце менее числа элементов в GF(2^8)?

 

За матрицу не беспокойся, это матрица знатная и известная, называется Cauchy matrix и есть в Вики на англисском.

Лучше наверное говорить что у матрицы 10 строк и 100 столбцов. Так вот, любая подматрица размером 10x10 и меньше будет обратимой и декодирование всегда возможно.

Я думаю меньше или равна 256, т.е. кодовое пространство можно юзать на всю катушку например взяв матрицу 26x230

 

во, нашел готовую таблицу умножения, вернее индексов для умножения =)))

Код (Text):

1. 000 001 255  043 119 218   086 177 219   129 023 112   172 123 220   215 239 170
2. 001 002   0   044 238 240   087 127 189   130 046 192   173 246 252   216 195 251
3. 002 004   1   045 193  18   088 254 241   131 092 247   174 241 190   217 155  96
4. 003 008  25   046 159 130   089 225 210   132 184 140   175 255  97   218 043 134
5. 004 016   2   047 035  69   090 223  19   133 109 128   176 227 242   219 086 177
6. 005 032  50   048 070  29   091 163  92   134 218  99   177 219  86   220 172 187
7. 006 064  26   049 140 181   092 091 131   135 169  13   178 171 211   221 069 204
8. 007 128 198   050 005 194   093 182  56   136 079 103   179 075 171   222 138  62
9. 008 029   3   051 010 125   094 113  70   137 158  74   180 150  20   223 009  90
10. 009 058 223   052 020 106   095 226  64   138 033 222   181 049  42   224 018 203
11. 010 116  51   053 040  39   096 217  30   139 066 237   182 098  93   225 036  89
12. 011 232 238   054 080 249   097 175  66   140 132  49   183 196 158   226 072  95
13. 012 205  27   055 160 185   098 067 182   141 021 197   184 149 132   227 144 176
14. 013 135 104   056 093 201   099 134 163   142 042 254   185 055  60   228 061 156
15. 014 019 199   057 186 154   100 017 195   143 084  24   186 110  57   229 122 169
16. 015 038  75   058 105   9   101 034  72   144 168 227   187 220  83   230 244 160
17. 016 076   4   059 210 120   102 068 126   145 077 165   188 165  71   231 245  81
18. 017 152 100   060 185  77   103 136 110   146 154 153   189 087 109   232 247  11
19. 018 045 224   061 111 228   104 013 107   147 041 119   190 174  65   233 243 245
20. 019 090  14   062 222 114   105 026  58   148 082  38   191 065 162   234 251  22
21. 020 180  52   063 161 166   106 052  40   149 164 184   192 130  31   235 235 235
22. 021 117 141   064 095   6   107 104  84   150 085 180   193 025  45   236 203 122
23. 022 234 239   065 190 191   108 208 250   151 170 124   194 050  67   237 139 117
24. 023 201 129   066 097 139   109 189 133   152 073  17   195 100 216   238 011  44
25. 024 143  28   067 194  98   110 103 186   153 146  68   196 200 183   239 022 215
26. 025 003 193   068 153 102   111 206  61   154 057 146   197 141 123   240 044  79
27. 026 006 105   069 047 221   112 129 202   155 114 217   198 007 164   241 088 174
28. 027 012 248   070 094  48   113 031  94   156 228  35   199 014 118   242 176 213
29. 028 024 200   071 188 253   114 062 155   157 213  32   200 028 196   243 125 233
30. 029 048   8   072 101 226   115 124 159   158 183 137   201 056  23   244 250 230
31. 030 096  76   073 202 152   116 248  10   159 115  46   202 112  73   245 233 231
32. 031 192 113   074 137  37   117 237  21   160 230  55   203 224 236   246 207 173
33. 032 157   5   075 015 179   118 199 121   161 209  63   204 221 127   247 131 232
34. 033 039 138   076 030  16   119 147  43   162 191 209   205 167  12   248 027 116
35. 034 078 101   077 060 145   120 059  78   163 099  91   206 083 111   249 054 214
36. 035 156  47   078 120  34   121 118 212   164 198 149   207 166 246   250 108 244
37. 036 037 225   079 240 136   122 236 229   165 145 188   208 081 108   251 216 234
38. 037 074  36   080 253  54   123 197 172   166 063 207   209 162 161   252 173 168
39. 038 148  15   081 231 208   124 151 115   167 126 205   210 089  59   253 071  80
40. 039 053  33   082 211 148   125 051 243   168 252 144   211 178  82   254 142  88
41. 040 106  53   083 187 206   126 102 167   169 229 135   212 121  41   255 000 175
42. 041 212 147   084 107 143   127 204  87   170 215 151   213 242 157
43. 042 181 142   085 214 150   128 133   7   171 179 178   214 249  85

 

persicum
Уже проверил, всё работает Для GF(2^8) нашёл 16 полиномов(половина - зеркальные отражения другой половины), мне больше всего нравится x^8+x^7+x^6+X+1, потому как симметричный если не учитывать x^8. Теперь можно всё это безобразие в контроллер запихивать.

 

правда чтоли? o:

А как декодирование организовали, двухпроходное с матрицей и ее подматрицей или однопроходное с матрицей дополненной единичными векторами до квадратной?

Осторожно еще с умножением на ноль, логарифма нуля не сусществует! Это просто заглушки в таблице. Впрочем, вы ее не лету строите как я понял.

 

Все гораздо проще, если нет пропаданий близких пакетов. 5-й рейд.
Передаете сообщения a,b,c и т.д одновременно считаете a XOR b xor c ... и передаете его в последний момент. Пропавший пакет относительно легко восстанавливается

Проще всего конечно a, b и a XOR b но избыточность большая - 30%