Кодирование треугольной сети - Triangular network coding

В теория кодирования, кодирование треугольной сети (TNC) это сетевое кодирование схема кодирования пакетов, представленная Куреши, Фох и Кай (2012).^[1]Ранее пакетное кодирование для сетевого кодирования выполнялось с использованием линейного сетевого кодирования (LNC). Недостаток LNC перед большим конечное поле в том, что это привело к высокому уровню кодирования и декодирования вычислительная сложность. При линейном кодировании и декодировании GF (2) снимает проблему высокой вычислительной сложности, кодирование с использованием GF (2) происходит за счет снижения производительности пропускной способности.

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

Кодирование и декодирование

Пример кодирования четырех пакетов с помощью TNC. Немного б_я,k ∈ {0,1} - это я^th немного k^th пакет. Каждый пакет имеет исходную длину B биты. Полученный закодированный пакет имеет длину B + 3 бита. Информация о количестве избыточных "0" битов, добавленных в заголовок каждого пакета, включается в заголовок закодированного пакета.

В TNC кодирование выполняется в два этапа. Первые избыточные "0" биты выборочно добавляются в начало и конец каждого пакета, так что все пакеты имеют одинаковую длину в битах. Тогда пакеты XOR кодируется, мало по малу. Биты «0» добавляются таким образом, что эти избыточные биты «0», добавленные к каждому пакету, генерируют треугольный узор.

По сути, процесс декодирования TNC, как и процесс декодирования LNC, включает Гауссово исключение. Однако, поскольку пакеты в TNC были закодированы таким образом, что результирующие закодированные пакеты имеют треугольную структуру, вычислительный процесс треугольная форма,^[2] со сложностью ${\displaystyle O(n^{3})}$, где ${\displaystyle n}$ - количество пакетов, которые можно обойти. Приемнику теперь нужно только выполнить обратная подстановка,^[2] со сложностью, заданной как ${\displaystyle O(n^{2})}$ для каждого битового местоположения.

использованная литература

1. Куреши, Джалалуддин; Фо, Чуан Хенг; Цай, Цзяньфэй (2012), «Оптимальное решение проблемы индексного кодирования с использованием сетевого кодирования через GF (2)», IEEE Secon: 134–142, arXiv:1209.6539, Bibcode:2012arXiv1209.6539Q, Дои:10.1109 / SECON.2012.6275780, ISBN  978-1-4673-1905-8.
2. Дж. Б. Фрали, Р. А. Борегар, Линейная алгебра. Глава 10, Addison-Wesley Publishing Company, 1995.