Лучшие тарифы

выгодный
3.5 руб/мин
безлимит
160 рублей
Безлимит на свои операторы
120 руб
Безлимит
299 руб
Замечательный тариф
99 руб

Реклама

Список терминов и летературы.

Список терминов и летературы.

ЭНЦИКЛОПЕДИЯ WiMAX ПУТЬ К 4G - В. Портной

L(Q) < QJ(4 -R- 1/Q).

Данная оценка вычислительной сложности алгоритма получена для последо­вательного вычислительного устройства, в котором в каждый момент времени выполняется одна элементарная операция. Далее будет оцениваться вычисли­тельная сложность алгоритма в предположении, что имеется «параллельное» вычислительное устройство, в котором в каждый момент времени может вы­полняться одновременно любое количество элементарных операций. Обозначим через L * (.V), L * (Q.N) и L * (Q) вычислительную сложность одной итерации, сложность всего алгоритма при Q итерациях и сложность на один кодовый символ при Q итерациях соответственно для параллельного вычислительного устройства.

Легко видеть, что для параллельного вычислительного устройства сложность предварительного вычисления синдрома приблизительно равна Jlog2 N. а слож­ность процедуры нормировки — log. Л'.

Поскольку в любой полосе проверочной матрицы каждый столбец содержит ровно одну единицу, все строки в одной полосе могут обрабатываться одно­временно. Следовательно, параллельная сложность обработки одной полосы не превышает ЪК + J — 2.

Таким образом.

L * (N) < J(3K' + J - 2) + log2 Лг.

L * (Q,N) s$ J log, N + QJ(iK + J - 2) + Qlog2 N, L*(Q)< ((J + Q) log, N + QJ(3K + .1- 2))/N.

В качестве примера рассмотрим низкоплотностный код дайной N = 4112, R = 0.75, J = 4, А' = 16. Пусть""при декодировании этого кода используется 10 итераций. Тогда с помощью приведенных формул находим, что в случае по­следовательного вычислительного устройства на один символ приходится 126 элементарных операций, в то время как для параллельного устройства не бо­лее 0.6 операции на один символ.

Хотя определенное выше параллельное вычислительное устройство является практически нереализуемым, поскольку требуется одновременное выполнение неограниченного числа элементарных операций, тем не менее результат, полу­ченный для этого устройства, имеет определенный практический смысл. Дело в том, что требуемая параллельность вычислений при реализации алгоритма декодирования ограничивается количеством строк в одной полосе проверочной матрицы, равным Р (в рассмотренном выше примере Р = 257). Таким образом, для достижения результата параллельного устройства, технически реализуемое устройство должно выполнять одновременную обработку Р строк в одной полосе проверочной матрицы.