Цифровые моды и все что с ними связано

UR5FFR
Site Admin
Posts: 2187
Joined: 21 Apr 2012, 22:00
Позывной: UR5FFR
Location: Odessa

Re: Цифровые моды и все что с ними связано

Post by UR5FFR »

При таком подходе нет посимвольной синхронизации - невозможно определить где начинается передаваемый байт. И синхронизацию придется делать в начале передачи блока данных.
Когда Justas шлет сообщение Alice, слушатель Piter должен дождаться начала нового блока чтобы начать декодировать данные. У меня Piter может начать читать передаваемые символы сразу же, не дожидаясь нового фрейма данных. В этом плане мой протокол больше похож на CW. А то что вы предлагаете - на пакетную передачу данных.
Теперь по полосе пропускания. У вас 24 бита. Манчестер удваивает требования к полосе.
lz5zi
Posts: 30
Joined: 10 Jan 2019, 07:57
Позывной: LZ5ZI

Re: Цифровые моды и все что с ними связано

Post by lz5zi »

Если у меня 6 битовой символ ето 18 битов. Полоса максимально х2 ( реално от 0.5 до 2 ) равняется 36.

Для посимвольной синхронизации, согласен.
UR5FFR
Site Admin
Posts: 2187
Joined: 21 Apr 2012, 22:00
Позывной: UR5FFR
Location: Odessa

Re: Цифровые моды и все что с ними связано

Post by UR5FFR »

Можно подойти к проблеме посимвольной синхронизации немного с другой стороны. Если у нас есть избыточный код то мы можем синхронизироваться по максимальному соответствию. Например, возьмем N-битовые данные, допишем к ним контрольную сумму размером M бит. Получим кодовые слова длиной N+M. Общее количество кодов 2^(N+M), при этом только 2^N из них корректные. Алгоритм пытается декодировать в битовом потоке несколько последовательных кодовых слов начиная с каждого бита потока. Позиция, когда корректно декодировано максимальное количество слов, принимается за границу кодового слова.

Пример реализации. Данные 6 бит дополняются до 8ми двумя битами контроля четности.

Code: Select all

01DDDDDD - количество 1 бит в DDDDDD четно
10DDDDDD - количество 1 бит в DDDDDD нечетно
Для кодирования пробела используется последовательность с хорошей автокорреляцией. Например 10101100.
Для более надежной синхронизации можно передавать символ пробела многократно если данные поступают нерегулярно (например вводятся с клавиатуры). На приемной стороне эти множественные пробелы отображаются как один символ.

Если не вводить избыточность для коррекции ошибок то скорость полученного код равно 3/4. При введении трехкратной избыточности и мажоритарном декодировании скорость уменьшается до 1/4. На 1 передаваемый символ требуется пакет в 24 бита. Код может исправить до 8 ошибок в пакете. При полосе 50гц реально достичь скорости передачи 24 WPM.

Для сравнения рассмотренный ранее код имел скорость соответственно 1/2 и 1/6. При той же полосе 50гц он может обеспечить скорость 16,5 WPM
UR5FFR
Site Admin
Posts: 2187
Joined: 21 Apr 2012, 22:00
Позывной: UR5FFR
Location: Odessa

Re: Цифровые моды и все что с ними связано

Post by UR5FFR »

Рассмотренные ранее коды являются каскадными, основой их является блочный код с расстоянием d>=2. Он детектирует ошибки, но он не может исправлять их из-за малого кодового расстояния. Логично сделать следующий шаг - использовать код с расстоянием d=3, который позволит исправлять одиночные ошибки и детектировать двойные.

Наиболее известные и простые в декодировании являются коды Хемминга с расстоянием d=3. Но у них есть ограничение на размер кодового слова - мы не можем построить код для любого размера данных и кодовых слов. Например известны коды Хемминга (7,4,3) и (15,11,3). Но нет кода Хемминга (11,6,3).

Для построения кодов исправляющих ошибки на данных рпроизвольной битности и с заданным кодовым расстоянием подходит класс нелинейных кодов. Самый простой метод построения такого кода - последовательно выбираем непромаркированные кодовые слова из пространства 2^N, для каждого слова маркируем его и все слова которые расположены рядом с ним на расстоянии Хемминга <=d. Повторяем процедуру пока не промаркируем все кодовые слова.

Для кодовых слов слов небольшого размера можно построить эффективный кодер-декодер используя lookup-таблицы. Рассмотрим логику его работы на примере кода с d=4 исправляющего одиночную ошибку. Принятое кодове слово проверяется на присутствие в таблице. Если его там нет - формируется множество кодовых слов с одиночной ошибкой и каждое из них проверяется на присутствие в таблице. Если мы нашли слово в таблице то или оно без ошибок или мы исправили одиночную ошибку. Если не нашли - значит ошибка двойная. Тройные ошибки не детектируются.

Затраты памяти для табличной реализации сравнительно умеренные. Например для кода (11,6,4) нам необходима таблица кодовых слов для передачи - 64 кодовых слова по 11 бит каждое = 64*16/8 = 128 байт. Для декодирования нам нужна таблица из 2048 однобитных элементов, которая отвечает является ли кодове слово корректным. Она потребует 2048*1/8 = 256 байт. Итого затраты 384 байта, что вполне реализуемо даже на микроконтроллерах с ограниченным количеством памяти.

Некоторые коды, которые могут представлять практический интерес

Код (11,6,4)

Code: Select all

Codeword bits 11
Codeword сount 64
Distance 4
0x004,0x00B,0x037,0x038,0x051,0x05E,0x062,0x06D,0x182,0x18D,0x1B1,0x1BE,0x1D7,0x1D8,0x1E4,0x1EB,
0x281,0x28E,0x2B2,0x2BD,0x2D4,0x2DB,0x2E7,0x2E8,0x307,0x308,0x334,0x33B,0x352,0x35D,0x361,0x36E,
0x490,0x49F,0x4A3,0x4AC,0x4C5,0x4CA,0x4F6,0x4F9,0x501,0x50E,0x532,0x53D,0x554,0x55B,0x567,0x568,
0x602,0x60D,0x631,0x63E,0x657,0x658,0x664,0x66B,0x784,0x78B,0x7B7,0x7B8,0x7D1,0x7DE,0x7E2,0x7ED
Код (12,7,4)

Code: Select all

Codeword bits 12
Codeword сount 128
Distance 4
0x107,0x108,0x134,0x13B,0x152,0x15D,0x161,0x16E,0x191,0x19E,0x1A2,0x1AD,0x1C4,0x1CB,0x1F7,0x1F8,
0x213,0x21C,0x220,0x22F,0x245,0x24A,0x276,0x279,0x286,0x289,0x2B5,0x2BA,0x2D0,0x2DF,0x2E3,0x2EC,
0x401,0x40E,0x432,0x43D,0x454,0x45B,0x467,0x468,0x497,0x498,0x4A4,0x4AB,0x4C2,0x4CD,0x4F1,0x4FE,
0x702,0x70D,0x731,0x73E,0x757,0x758,0x764,0x76B,0x794,0x79B,0x7A7,0x7A8,0x7C1,0x7CE,0x7F2,0x7FD,
0x802,0x80D,0x831,0x83E,0x857,0x858,0x864,0x86B,0x894,0x89B,0x8A7,0x8A8,0x8C1,0x8CE,0x8F2,0x8FD,
0xB01,0xB0E,0xB32,0xB3D,0xB54,0xB5B,0xB67,0xB68,0xB97,0xB98,0xBA4,0xBAB,0xBC2,0xBCD,0xBF1,0xBFE,
0xD04,0xD0B,0xD37,0xD38,0xD51,0xD5E,0xD62,0xD6D,0xD92,0xD9D,0xDA1,0xDAE,0xDC7,0xDC8,0xDF4,0xDFB,
0xE07,0xE08,0xE34,0xE3B,0xE52,0xE5D,0xE61,0xE6E,0xE91,0xE9E,0xEA2,0xEAD,0xEC4,0xECB,0xEF7,0xEF8
Код (13,8,4)

Code: Select all

Codeword bits 13
Codeword сount 256
Distance 4
0x0115,0x011A,0x0126,0x0129,0x0140,0x014F,0x0173,0x017C,0x0183,0x018C,0x01B0,0x01BF,0x01D6,0x01D9,0x01E5,0x01EA,
0x0216,0x0219,0x0225,0x022A,0x0243,0x024C,0x0270,0x027F,0x0280,0x028F,0x02B3,0x02BC,0x02D5,0x02DA,0x02E6,0x02E9,
0x0401,0x040E,0x0432,0x043D,0x0454,0x045B,0x0467,0x0468,0x0497,0x0498,0x04A4,0x04AB,0x04C2,0x04CD,0x04F1,0x04FE,
0x0702,0x070D,0x0731,0x073E,0x0757,0x0758,0x0764,0x076B,0x0794,0x079B,0x07A7,0x07A8,0x07C1,0x07CE,0x07F2,0x07FD,
0x0802,0x080D,0x0831,0x083E,0x0857,0x0858,0x0864,0x086B,0x0894,0x089B,0x08A7,0x08A8,0x08C1,0x08CE,0x08F2,0x08FD,
0x0B01,0x0B0E,0x0B32,0x0B3D,0x0B54,0x0B5B,0x0B67,0x0B68,0x0B97,0x0B98,0x0BA4,0x0BAB,0x0BC2,0x0BCD,0x0BF1,0x0BFE,
0x0D04,0x0D0B,0x0D37,0x0D38,0x0D51,0x0D5E,0x0D62,0x0D6D,0x0D92,0x0D9D,0x0DA1,0x0DAE,0x0DC7,0x0DC8,0x0DF4,0x0DFB,
0x0E07,0x0E08,0x0E34,0x0E3B,0x0E52,0x0E5D,0x0E61,0x0E6E,0x0E91,0x0E9E,0x0EA2,0x0EAD,0x0EC4,0x0ECB,0x0EF7,0x0EF8,
0x1004,0x100B,0x1037,0x1038,0x1051,0x105E,0x1062,0x106D,0x1092,0x109D,0x10A1,0x10AE,0x10C7,0x10C8,0x10F4,0x10FB,
0x1307,0x1308,0x1334,0x133B,0x1352,0x135D,0x1361,0x136E,0x1391,0x139E,0x13A2,0x13AD,0x13C4,0x13CB,0x13F7,0x13F8,
0x1510,0x151F,0x1523,0x152C,0x1545,0x154A,0x1576,0x1579,0x1586,0x1589,0x15B5,0x15BA,0x15D3,0x15DC,0x15E0,0x15EF,
0x1613,0x161C,0x1620,0x162F,0x1646,0x1649,0x1675,0x167A,0x1685,0x168A,0x16B6,0x16B9,0x16D0,0x16DF,0x16E3,0x16EC,
0x1913,0x191C,0x1920,0x192F,0x1946,0x1949,0x1975,0x197A,0x1985,0x198A,0x19B6,0x19B9,0x19D0,0x19DF,0x19E3,0x19EC,
0x1A10,0x1A1F,0x1A23,0x1A2C,0x1A45,0x1A4A,0x1A76,0x1A79,0x1A86,0x1A89,0x1AB5,0x1ABA,0x1AD3,0x1ADC,0x1AE0,0x1AEF,
0x1C15,0x1C1A,0x1C26,0x1C29,0x1C40,0x1C4F,0x1C73,0x1C7C,0x1C83,0x1C8C,0x1CB0,0x1CBF,0x1CD6,0x1CD9,0x1CE5,0x1CEA,
0x1F16,0x1F19,0x1F25,0x1F2A,0x1F43,0x1F4C,0x1F70,0x1F7F,0x1F80,0x1F8F,0x1FB3,0x1FBC,0x1FD5,0x1FDA,0x1FE6,0x1FE9
Для большей надежности можно увеличить длину кода на 1 бит, добавив к нему бит четности. При этом количество исправляемых ошибок не увеличивается, но улучшается обнаружение двойных ошибок.

Коды можно строить и с большим расстоянием. Но это приводит к увеличению длины кодовых слов. При этом построенный с помощью описанной выше процедуры код может иметь дробную битность. Например следующий код используя 48 кодовых слов (~= 5.6 бит), каждое длинной 14 бит, исправляет двойные ошибки и детектирует тройные. 48 символов достаточно чтобы передать латинский алфавит, цифры и основные знаки пунктуации.

Код (14,5.6,6)

Code: Select all

Codeword bits 14
Codeword сount 48
Distance 6
0x00E8,0x0101,0x013E,0x0246,0x029B,0x03F5,0x045D,0x04A7,0x05D2,0x0630,0x076B,0x078C,0x0873,0x0894,0x09CF,0x0A2D,
0x0B58,0x0BA2,0x0C0A,0x0D64,0x0DB9,0x0EC1,0x0EFE,0x0F17,0x300C,0x30B1,0x3157,0x327A,0x33AF,0x33C0,0x34CB,0x3522,
0x35FC,0x3665,0x3696,0x3719,0x38E6,0x3969,0x399A,0x3A03,0x3ADD,0x3B34,0x3C3F,0x3C50,0x3D85,0x3EA8,0x3F4E,0x3FF3
Еще один код с дробной битностью данных и расстоянием 6.

Код (15,6.2,6)

Code: Select all

Codeword bits 15
Codeword сount 74
Distance 6
0x10E8,0x1101,0x113E,0x1246,0x129B,0x13F5,0x145D,0x14A7,0x15D2,0x1630,0x176B,0x178C,0x1873,0x1894,0x19CF,0x1A2D,
0x1B58,0x1BA2,0x1C0A,0x1D64,0x1DB9,0x1EC1,0x1EFE,0x1F17,0x200C,0x20B1,0x2157,0x227A,0x23AF,0x23C0,0x24CB,0x2522,
0x25FC,0x2665,0x2696,0x2719,0x28E6,0x2969,0x299A,0x2A03,0x2ADD,0x2B34,0x2C3F,0x2C50,0x2D85,0x2EA8,0x2F4E,0x2FF3,
0x4012,0x406F,0x419D,0x42A4,0x4548,0x46F9,0x4776,0x4783,0x49F0,0x4ACA,0x4B3B,0x4B45,0x4C21,0x4CD7,0x4DAE,0x4E1C,
0x7074,0x7186,0x71FB,0x7249,0x7498,0x752D,0x76E2,0x7AB7,0x7BEC,0x7D43
По поводу выбора кодового расстояния. Чтобы исправить k ошибок требуется код с расстоянием d >= 2*k+1.
Если нам требуется чтобы код исправлял k ошибок и обнаруживал k+1 ошибок то потребуется код с расстоянием d >= 2*k+2.
Соответственно зависимость возможностей кода от расстояния такие:

Code: Select all

d=2    обнаружение однократных ошибок
d=3    исправление однократных ошибок
d=4    исправление однократных и обнаружение двойных ошибок
d=5    исправление однократных и двойных ошибок
d=6    исправление однократных и двойных ошибок. обнаружение тройных ошибок
Описанные нелинейные коды более оптимальный чем циклические, порождаемые примитивным полиномом степени n-k. Например мы можем создать циклический код (11,6) или (11,7). В обеих случаях кодовое расстояние будет равно трем. Для нелинейного кода оно равно 4. В результате нелинейный код может так же обнаруживать двойную ошибку. Аналогично циклические коды (15,7) и (15,6) имеют кодовое расстояние 5. В то время как нелинейный код (15,6.2,6) имеет расстояние 6.
Post Reply