Треугольное сетевое кодирование

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

Основной вклад треугольного сетевого кодирования заключается в уменьшении вычислительной сложности декодирования в худшем случае. $O(n^{3})$ к $O(n^{2})$ (где n — общее количество пакетов данных, кодируемых в кодированном пакете) без ухудшения пропускной способности, со скоростью кода , сравнимой со скоростью кодирования оптимальных схем кодирования.

Треугольный код также был предложен в качестве кода Фонтана. ^[2] для достижения почти оптимальной производительности при кодировании и декодировании вычислительной сложности $O(n\log n)$ . Далее было показано, что фонтанный код на основе треугольников может даже превосходить по производительности оптимизированный код преобразования Луби . ^[2]

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

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

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

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

Ссылки

^ Куреши, Джалалуддин; Фо, Чуан Хэн; Цай, Цзяньфэй (2012). «Оптимальное решение проблемы индексного кодирования с использованием сетевого кодирования через GF (2)». 2012 9-я ежегодная конференция IEEE Communications Society по сенсорным, ячеистым и специальным коммуникациям и сетям (SECON) . стр. 134–142. arXiv : 1209.6539 . Бибкод : 2012arXiv1209.6539Q . дои : 10.1109/SECON.2012.6275780 . ISBN 978-1-4673-1905-8 . S2CID 8977891 . .
^ Jump up to: ^а ^б Куреши, Джалалуддин; Фо, Чуан Хэн (август 2023 г.). «Треугольный код: почти оптимальный код фонтана линейного времени» . Цифровые коммуникации и сети . 9 (4): 869–878. дои : 10.1016/j.dcan.2022.12.006 .
^ Jump up to: ^а ^б Дж. Б. Фрэли и Р. А. Борегар, Линейная алгебра. Глава 10, Издательство Addison-Wesley, 1995.

о телекоммуникациях незавершена . Эта статья Вы можете помочь Википедии, расширив ее .

[1] Куреши, Джалалуддин; Фо, Чуан Хэн; Цай, Цзяньфэй (2012). «Оптимальное решение проблемы индексного кодирования с использованием сетевого кодирования через GF (2)». 2012 9-я ежегодная конференция IEEE Communications Society по сенсорным, ячеистым и специальным коммуникациям и сетям (SECON) . стр. 134–142. arXiv : 1209.6539 . Бибкод : 2012arXiv1209.6539Q . дои : 10.1109/SECON.2012.6275780 . ISBN 978-1-4673-1905-8 . S2CID 8977891 . .

[journal-article-2] Jump up to: ^а ^б Куреши, Джалалуддин; Фо, Чуан Хэн (август 2023 г.). «Треугольный код: почти оптимальный код фонтана линейного времени» . Цифровые коммуникации и сети . 9 (4): 869–878. дои : 10.1016/j.dcan.2022.12.006 .

[fraleigh95-3] Jump up to: ^а ^б Дж. Б. Фрэли и Р. А. Борегар, Линейная алгебра. Глава 10, Издательство Addison-Wesley, 1995.

[1]

[2]

[3]