Cтраница 4
Предположим теперь, что при передаче по ДСК ( см. рис. 5.3.1, а) с переходной вероятностью е 1 / 2 используется систематический код с проверкой на четность. Число позиций, в которых отличаются две двоичные последовательности, называется расстоянием Хэмминга между этими последовательностями. Нетрудно видеть, что Pr ( y xm) - убывающая функция от расстояния Хэмминга между у и хт, и поэтому декодирование по максимуму правдоподобия эквивалентно выбору кодового слова, находящегося на минимальном расстоянии от у. Отметим также, что расстояние между у и хт равно числу единиц ( называемому весом) в шумовой последовательности zm уфхт. Декодирование по максимуму правдоподобия состоит в выборе кодового слова хт, для которого zm yCB Xm имеет минимальный вес. [46]
Передаточную функцию пути abce ( который начинается и заканчивается в состоянии 00) можно рассчитать через неопределенный заполнитель D как C. Степень D - общее число единиц на пути, а значит, расстояние Хэмминга до нулевого пути. Точно так же пути abd с е и a be bee имеют передаточную функцию D6 и, соответственно, расстояние Хэмминга, равное 6, до нулевого пути. [47]
Для простоты предположим, что мы имеем дело с каналом BSC; в таком случае приемлемой мерой расстояния будет расстояние Хэмминга. Кодер для этого примера показан на рис. 7.3, а решетчатая диаграмма - на рис. 7.7. Для представления декодера, как показано на рис. 7.10, можно воспользоваться подобной решеткой. Поскольку в этом примере возможны только два перехода, разрешающих другое состояние, для начала не нужно показывать все ветви. Принцип работы происходящего после процедуры декодирования можно понять, изучив решетку кодера на рис. 7.7 и решетку декодера, показанную на рис. 7.10. Для решетки декодера каждую ветвь за каждый временной интервал удобно пометить расстоянием Хэмминга между полученным кодовым символом и кодовым словом, соответствующим той же ветви из решетки кодера. Как показано на рис. 7.3, кодер характеризуется кодовыми словами, находящимися на ветвях решетки кодера и заведомо известными как кодеру, так и декодеру. Эти слова являются кодовыми символами, которые можно было бы ожидать на выходе кодера в результате каждого перехода между состояниями. Пометки на ветвях решетки декодера накапливаются декодером в процессе. Другими словами, когда получен кодовый символ, каждая ветвь решетки декодера помечается метрикой подобия ( расстоянием Хэмминга) между полученным кодовым символом и каждым словом ветви за этот временной интервал. Глядя вновь на решетку кодера, видим, что переход между состояниями 00 - 10 порождает на выходе кодовое слово 11, точно соответствующее полученному в момент г, кодовому символу. В итоге, метрика входящих в решетку декодера ветвей описывает разницу ( расстояние) между тем, что было получено, и тем, что могло бы быть получено, имея кодовые слова, связанные с теми ветвями, с которых они были переданы. По сути, эти метрики описывают величину, подобную корреляциям между полученным кодовым словом и каждым из кандидатов на роль кодового слова. В алгоритме декодирования эти метрики расстояния Хэмминга используются для нахождения наиболее вероятного ( с минимальным расстоянием) пути через решетку. [48]
Конечно же, понятно, что правильно декодировать можно не все модели ошибки. Возможности кода для исправления ошибок в первую очередь определяются его структурой. Весовой коэффициент Хэмминга ( Hamming weight) w ( U) кодового слова U определяется как число ненулевых элементов в U. Для двоичного вектора это эквивалентно числу единиц в векторе. Расстояние Хэмминга ( Hamming distance) между двумя кодовыми словами U и V, обозначаемое как d ( U, V), определяется как количество элементов, в которых они отличаются. [49]
Была предпринята попытка рассмотреть проблему описания совокупности генерированных завершенных структур. Важно знать, к примеру, частоту появления стеблей в совокупности. Один или же больше стеблей встречаются всегда. Для часто появляющихся стеблей характерно отражение инвариантных аспектов скручивания. То же самое можно сказать о статистике, соответствующей частоте, с которой расположения отдельных оснований появляются в спаренной форме. Для этого удобно соотнести каждой найденной завершенной структуре двоичную последовательность, в которой элемент в / - м положении равен единице, если 1 - е основание появляется спаренным с другим, и нулю - в противном случае. Тогда мы можем определить расстояние между структурами просто как расстояние Хэмминга между их двоичными последовательностями. Затем можно легко обратиться к методологии кла-стерирования с целью нахождения кластеров внутри данной совокупности. Для некоторых образцов РНК был осуществлен кластерный анализ, но он носил главным образом предварительный характер в ожидании более тщательного обоснования нашего подхода при использовании метода Монте-Карло. Следует также отметить, что обсуждение, проведенное при кластерном анализе, основано на перечнях свойств, в рамках которых генерируется вектор для каждой структуры в зависимости от наличия или отсутствия определенных свойств. Интерес представляет, например, перечень свойств, характеризующих симметрию структуры. До сих пор в этом направлении был достигнут незначительный прогресс, но он представляется многообещающим. [50]
Для простоты предположим, что мы имеем дело с каналом BSC; в таком случае приемлемой мерой расстояния будет расстояние Хэмминга. Кодер для этого примера показан на рис. 7.3, а решетчатая диаграмма - на рис. 7.7. Для представления декодера, как показано на рис. 7.10, можно воспользоваться подобной решеткой. Поскольку в этом примере возможны только два перехода, разрешающих другое состояние, для начала не нужно показывать все ветви. Принцип работы происходящего после процедуры декодирования можно понять, изучив решетку кодера на рис. 7.7 и решетку декодера, показанную на рис. 7.10. Для решетки декодера каждую ветвь за каждый временной интервал удобно пометить расстоянием Хэмминга между полученным кодовым символом и кодовым словом, соответствующим той же ветви из решетки кодера. Как показано на рис. 7.3, кодер характеризуется кодовыми словами, находящимися на ветвях решетки кодера и заведомо известными как кодеру, так и декодеру. Эти слова являются кодовыми символами, которые можно было бы ожидать на выходе кодера в результате каждого перехода между состояниями. Пометки на ветвях решетки декодера накапливаются декодером в процессе. Другими словами, когда получен кодовый символ, каждая ветвь решетки декодера помечается метрикой подобия ( расстоянием Хэмминга) между полученным кодовым символом и каждым словом ветви за этот временной интервал. Глядя вновь на решетку кодера, видим, что переход между состояниями 00 - 10 порождает на выходе кодовое слово 11, точно соответствующее полученному в момент г, кодовому символу. В итоге, метрика входящих в решетку декодера ветвей описывает разницу ( расстояние) между тем, что было получено, и тем, что могло бы быть получено, имея кодовые слова, связанные с теми ветвями, с которых они были переданы. По сути, эти метрики описывают величину, подобную корреляциям между полученным кодовым словом и каждым из кандидатов на роль кодового слова. В алгоритме декодирования эти метрики расстояния Хэмминга используются для нахождения наиболее вероятного ( с минимальным расстоянием) пути через решетку. [51]
Для простоты предположим, что мы имеем дело с каналом BSC; в таком случае приемлемой мерой расстояния будет расстояние Хэмминга. Кодер для этого примера показан на рис. 7.3, а решетчатая диаграмма - на рис. 7.7. Для представления декодера, как показано на рис. 7.10, можно воспользоваться подобной решеткой. Поскольку в этом примере возможны только два перехода, разрешающих другое состояние, для начала не нужно показывать все ветви. Принцип работы происходящего после процедуры декодирования можно понять, изучив решетку кодера на рис. 7.7 и решетку декодера, показанную на рис. 7.10. Для решетки декодера каждую ветвь за каждый временной интервал удобно пометить расстоянием Хэмминга между полученным кодовым символом и кодовым словом, соответствующим той же ветви из решетки кодера. Как показано на рис. 7.3, кодер характеризуется кодовыми словами, находящимися на ветвях решетки кодера и заведомо известными как кодеру, так и декодеру. Эти слова являются кодовыми символами, которые можно было бы ожидать на выходе кодера в результате каждого перехода между состояниями. Пометки на ветвях решетки декодера накапливаются декодером в процессе. Другими словами, когда получен кодовый символ, каждая ветвь решетки декодера помечается метрикой подобия ( расстоянием Хэмминга) между полученным кодовым символом и каждым словом ветви за этот временной интервал. Глядя вновь на решетку кодера, видим, что переход между состояниями 00 - 10 порождает на выходе кодовое слово 11, точно соответствующее полученному в момент г, кодовому символу. В итоге, метрика входящих в решетку декодера ветвей описывает разницу ( расстояние) между тем, что было получено, и тем, что могло бы быть получено, имея кодовые слова, связанные с теми ветвями, с которых они были переданы. По сути, эти метрики описывают величину, подобную корреляциям между полученным кодовым словом и каждым из кандидатов на роль кодового слова. В алгоритме декодирования эти метрики расстояния Хэмминга используются для нахождения наиболее вероятного ( с минимальным расстоянием) пути через решетку. [52]