Программная реализация кодера свёрточного кода и декодера по алгоритму Витерби

Namespace Viterbi

    ''' <summary>
    ''' Базовый класс для кодера и декодера Витерби.
    ''' </summary>
    Public MustInherit Class ViterbiBase

#Region "CTOR"

        ''' <summary>
        ''' Конструктор кодера с указанием порождающих многочленов.
        ''' </summary>
        ''' <param name="polynoms">Массив порождающих многочленов (по умолчанию в ВОСЬМЕРИЧНОЙ системе счисления).</param>
        ''' <param name="base">Основание системы счисления, в которой указаны полиномы. Обычно 8 или 10.</param>
        Public Sub New(polynoms() As Integer, base As Integer)
            Select Case base
                Case 10
                    Me.Polynoms = polynoms
                Case Else
                    ReDim Me.Polynoms(polynoms.Length - 1)
                    For i As Integer = 0 To polynoms.Length - 1
                        Me.Polynoms(i) = ConvertFromTo(polynoms(i), base, 10)
                    Next
            End Select
        End Sub

#End Region '/CTOR

#Region "PROPS"

        ''' <summary>
        ''' Массив порождающих многочленов.
        ''' </summary>
        Public ReadOnly Property Polynoms As Integer()

        ''' <summary>
        ''' Разрядность кодера.
        ''' </summary>
        ''' <remarks>Соответствует числу полиномов.</remarks>
        Public ReadOnly Property CoderBitness As Integer
            Get
                Return Polynoms.Length
            End Get
        End Property

        ''' <summary>
        ''' Разрядность сдвигового регистра кодера.
        ''' </summary>
        Public ReadOnly Property RegisterLength As Integer
            Get
                If (_RegisterLength = -1) Then
                    Dim maxPolynom As Integer = Polynoms.Max() 'определяем разрядность регистра по наибольшему числу
                    Dim tmp As Integer = ConvertFromTo(maxPolynom, 10, 2, _RegisterLength) 'для определения разрядности регистра
                End If
                Return _RegisterLength
            End Get
        End Property
        Private _RegisterLength As Integer = -1

        ''' <summary>
        ''' Таблица возможных состояний кодера.
        ''' </summary>
        Public ReadOnly Property CoderStates As Dictionary(Of Integer, Integer)
            Get
                If (_CoderStates.Count = 0) Then
                    _CoderStates = CalculateCoderStates()
                End If
                Return _CoderStates
            End Get
        End Property
        Private _CoderStates As New Dictionary(Of Integer, Integer)

        ''' <summary>
        ''' Таблица переходов кодера.
        ''' </summary>
        ''' <remarks>
        ''' Пользуясь решёткой, легко проводить кодирование, не высчитывая каждый раз суммы по модулю два. 
        ''' Для этого нужно взять за исходное состояние узел 000 и далее перемещаться по стрелкам в один из двух узлов. 
        ''' Выбор следующего узла определяется кодируемым битом данных – если бит данных «1», то первый слева бит следующего узла должен быть «1», 
        ''' если кодируемый бит – «0», то первый слева бит следующего узла должен быть «0». 
        ''' Физически переход соответствует сдвигу в регистре кодера. 
        ''' Выходным значением кодера будет (<see cref="Transition.CoderOut"/>).
        ''' </remarks>
        Public ReadOnly Property Transitions As Lookup(Of Integer, Transition)
            Get
                If (_Transitions Is Nothing) Then
                    _Transitions = CalculateTransitionsGrid()
                End If
                Return _Transitions
            End Get
        End Property
        Private _Transitions As Lookup(Of Integer, Transition) = Nothing

        ''' <summary>
        ''' Число возможных состояний регистра.
        ''' </summary>
        ''' <remarks>Всего 2^k ветвей (число заваисит только от длины регистра).</remarks>
        Protected ReadOnly Property StatesCount As Integer
            Get
                If (_StatesCount = 0) Then
                    _StatesCount = CInt(Math.Pow(2, RegisterLength))
                End If
                Return _StatesCount
            End Get
        End Property
        Private _StatesCount As Integer = 0

        ''' <summary>
        ''' Число возможных переходов из узла в узел / число узлов в решётке переходов
        ''' </summary>
        ''' <remarks>Всего 2^(k-1) переходов (число заваисит только от длины регистра).</remarks>
        Protected ReadOnly Property TransitionsCount As Integer
            Get
                If (_TransitionNodesCount = 0) Then
                    _TransitionNodesCount = CInt(Math.Pow(2, RegisterLength - 1))
                End If
                Return _TransitionNodesCount
            End Get
        End Property
        Private _TransitionNodesCount As Integer = 0

#End Region '/PROPS

#Region "METHODS"

        ''' <summary>
        ''' Возвращает список образующих многочленов в восьмеричной форме.
        ''' </summary>
        Public Overloads Function ToString() As String
            Dim sb As New Text.StringBuilder()
            sb.Append("(")
            For Each p As Integer In Polynoms
                sb.Append($"{p.ToOctal()},")
            Next
            sb = sb.Remove(sb.Length - 1, 1)
            sb.Append(")")
            Return sb.ToString()
        End Function

#End Region '/METHODS

#Region "CLOSED METHODS"

        ''' <summary>
        ''' Рассчитывает таблицу всех возможных состояний кодера.
        ''' </summary>
        ''' <remarks>Значение состояния определяется по его индексу.</remarks>
        Private Function CalculateCoderStates() As Dictionary(Of Integer, Integer)
            Dim states As New Dictionary(Of Integer, Integer) 'ключ словаря = номер состояния, значение = само состояние
            states.Add(0, 0) 'исходное состояние

            For stateNumber As Integer = 1 To StatesCount - 1 'начинаем с 1-го, т.к. 0-ое добавили выше
                Dim adderOuts As New List(Of Boolean)(Polynoms.Length) 'возможные значения выхода - по количеству сумматоров (или полиномов)
                For Each polynom As Integer In Polynoms 'рассчитываем каждое значение выхода: XORим между собой те биты содержимого регистра, на которые указывают "1" полинома
                    Dim adderOut As Boolean = False 'состояние выхода сумматора
                    Dim register As New BitArray({stateNumber}) 'содержимое регистра кодера = значение номера состояния
                    For i As Integer = 0 To RegisterLength - 1 'идём по всем битам регистра кодера
                        Dim polynomBit As Boolean = (((polynom >> i) And 1) > 0) 'i-ый бит полинома
                        If polynomBit Then 'если бит "1", то XORим значение i-го бита регистра с предыдущим значением выхода сумматора
                            adderOut = adderOut Xor register(i)
                        End If
                    Next
                    adderOuts.Add(adderOut)
                Next

                'Объединяем все выходы в одно состояние:
                Dim state As Integer = 0
                For Each adderOut In adderOuts
                    Dim currentBit As Integer = (CInt(adderOut) And 1)
                    state = (state << 1) Or currentBit
                Next

                states.Add(stateNumber, state)
            Next
            Return states
        End Function

        ''' <summary>
        ''' Рассчитывает решётку переходов.
        ''' </summary>
        Private Function CalculateTransitionsGrid() As Lookup(Of Integer, Transition)
            Dim transitions As New List(Of Transition)(TransitionsCount)
            For node As Integer = 0 To TransitionsCount - 1 'все числа от 0 до 2^(k-1)-1 - это значения узлов
                For mostSignificantBit As Integer = 0 To 1
                    Dim reg As Integer = node Or (mostSignificantBit << (RegisterLength - 1)) 'старший бит заменяем "0" или "1"
                    Dim coderOut As Integer = CoderStates(reg)
                    Dim destinationNode As Integer = reg >> 1
                    transitions.Add(New Transition(RegisterLength, Polynoms.Count, node, destinationNode, coderOut))
                Next
            Next
            Dim ilu As ILookup(Of Integer, Transition) = transitions.ToLookup(Of Integer, Transition)(
                Function(trans) trans.SourceNode, 'ключ - значение стартового узла
                Function(trans) trans 'значение - параметры (узел назначения, выход кодера)
                )
            Dim lu As Lookup(Of Integer, Transition) = CType(ilu, Lookup(Of Integer, Transition))
            Return lu
        End Function

        ''' <summary>
        ''' Выбирает узел решётки, в который нужно идти при кодировании бита <paramref name="bitToEncode"/>.
        ''' </summary>
        ''' <param name="bitToEncode">Очередной кодируемый бит сообщения.</param>
        ''' <param name="currentTransitions">Массив возможных переходов из текущего узла.</param>
        Protected Function GetNextTransition(bitToEncode As Boolean, currentTransitions As IEnumerable(Of Transition)) As Transition
            For Each t In currentTransitions
                Select Case bitToEncode
                    Case True 'если бит "1", то переход в узел со старшим битом "1"
                        If t.DestinationNodeMsb Then
                            Return t
                        End If
                    Case False 'если бит "0", то переход в узел со старшим битом "0"
                        If (Not t.DestinationNodeMsb) Then
                            Return t
                        End If
                End Select
            Next
            Return Nothing
        End Function

#End Region '/CLOSED METHODS

    End Class '/ViterbiBase

    ''' <summary>
    ''' Параметры перехода кодера.
    ''' </summary>
    Public Class Transition

#Region "CTOR"

        ''' <summary>
        ''' 
        ''' </summary>
        ''' <param name="registerBitness">Разрядность регистра.</param>
        ''' <param name="coderBitness">Разрядность кодера. Совпадает с числом порождающих многочленов кодера.</param>
        ''' <param name="srcNode">Исходящий узел.</param>
        ''' <param name="destNode">Входящий узел.</param>
        ''' <param name="coderOut">Значение на выходе кодера.</param>
        Public Sub New(registerBitness As Integer, coderBitness As Integer, srcNode As Integer, destNode As Integer, coderOut As Integer)
            Me.RegisterBitness = registerBitness
            Me.CoderBitness = coderBitness
            Me.SourceNode = srcNode
            Me.DestinationNode = destNode
            Me.CoderOut = coderOut
        End Sub

#End Region '/CTOR

#Region "PROPS"

        ''' <summary>
        ''' Значение узла, из которого осуществляется переход.
        ''' </summary>
        Public ReadOnly Property SourceNode As Integer

        ''' <summary>
        ''' Значение узла, в который возможен переход.
        ''' </summary>
        Public ReadOnly Property DestinationNode As Integer

        ''' <summary>
        ''' Выход кодера в виде битов.
        ''' </summary>
        Public ReadOnly Property CoderOutBits As Boolean()
            Get
                If (_CoderOutBits.Length = 0) Then
                    ReDim _CoderOutBits(CoderBitness - 1)
                    For i As Integer = 0 To CoderBitness - 1
                        Dim shift As Integer = CoderBitness - 1 - i
                        _CoderOutBits(i) = CBool((CoderOut >> shift) And 1)
                    Next
                End If
                Return _CoderOutBits
            End Get
        End Property
        Private _CoderOutBits() As Boolean = {}

        ''' <summary>
        ''' Старший бит узла назначения.
        ''' </summary>
        ''' <remarks>Используется при принятии решения о переходе.</remarks>
        Public ReadOnly Property DestinationNodeMsb As Boolean
            Get
                If (_DestinationNodeMsb Is Nothing) Then
                    Dim firstBit As Integer = DestinationNode >> (RegisterBitness - 2)
                    _DestinationNodeMsb = (firstBit > 0)
                End If
                Return _DestinationNodeMsb.Value
            End Get
        End Property
        Private _DestinationNodeMsb As Boolean? = Nothing

        ''' <summary>
        ''' Метрика пути.
        ''' </summary>
        ''' <remarks>Используется декодером.</remarks>
        Public Property Metrics As Integer = 0

#End Region '/PROPS

#Region "FIELDS"

        ''' <summary>
        ''' Разрядность кодера. Соответствует числу образующих многочленов.
        ''' </summary>
        Private ReadOnly CoderBitness As Integer

        ''' <summary>
        ''' Разрядность регистра.
        ''' </summary>
        Private ReadOnly RegisterBitness As Integer

        ''' <summary>
        ''' Значение на выходе кодера на данном переходе.
        ''' </summary>
        Private ReadOnly CoderOut As Integer

#End Region '/FIELDS

#Region "METHODS"

        ''' <summary>
        ''' Клонирует переход.
        ''' </summary>
        Public Function Clone() As Transition
            Dim cloned As Transition = CType(Me.MemberwiseClone(), Transition)
            cloned.Metrics = Me.Metrics
            Return cloned
        End Function

        Public Overloads Function ToString() As String
            Dim sb As New Text.StringBuilder()
            sb.Append(Convert.ToString(SourceNode, 2).PadLeft(CoderBitness + 1, "0"c))
            sb.Append("; ")
            sb.Append(Convert.ToString(DestinationNode, 2).PadLeft(CoderBitness + 1, "0"c))
            sb.Append("; ")
            sb.Append($"({Metrics})")
            Return sb.ToString()
        End Function

#End Region '/METHODS

    End Class '/Transition

    ''' <summary>
    ''' Вспомогательные методы.
    ''' </summary>
    <Runtime.CompilerServices.Extension()>
    Public Module Helpers

        ''' <summary>
        ''' Преобразует число из десятичной системы счисления в число в двоичной системе счисления.
        ''' </summary>
        <Runtime.CompilerServices.Extension()>
        Public Function ToBinary(dec As Integer) As Integer
            Return ConvertFromTo(dec, 10, 2)
        End Function

        ''' <summary>
        ''' Преобразует число из десятичной системы счисления в число в восьмеричной системе счисления.
        ''' </summary>
        <Runtime.CompilerServices.Extension()>
        Public Function ToOctal(dec As Integer) As Integer
            Return ConvertFromTo(dec, 10, 8)
        End Function

        ''' <summary>
        ''' Преобразует число из восьмеричной системы счисления в число в десятичной системе счисления.
        ''' </summary>
        <Runtime.CompilerServices.Extension()>
        Public Function ToDecimal(oct As Integer) As Integer
            Return ConvertFromTo(oct, 8, 10)
        End Function

        ''' <summary>
        ''' Преобразует число из одной системы счисления в другую.
        ''' </summary>
        ''' <param name="number">Число в исходной системе счисления.</param>
        ''' <param name="fromBase">Исходная система счисления.</param>
        ''' <param name="toBase">Целевая система счисления.</param>
        ''' <param name="bitness">Выходное значение - разрядность в целевой системе счисления. Если не требуется, можно не передавать.</param>
        ''' <remarks>
        ''' Будьте внимательны: при переводе в двоичную систему может возникнуть ошибка переполнения, т.к. двоичные числа очень длинные.
        ''' Перевод в 16-ную систему и обратно не обрабатывается.
        ''' </remarks>
        Public Function ConvertFromTo(number As Integer, fromBase As Integer, toBase As Integer, Optional ByRef bitness As Integer = 0) As Integer
            Dim result As Integer = 0
            Dim i As Integer = 0
            Do While (number <> 0)
                result += (number Mod toBase) * CInt(Math.Pow(fromBase, i))
                number = CInt(Math.Truncate(number / toBase))
                i += 1
            Loop
            bitness = i
            Return result
        End Function

        ''' <summary>
        ''' Возвращает строку, представляющую двоичную последовательность переданной строки.
        ''' </summary>
        ''' <param name="s">Произвольная строка.</param>
        <Runtime.CompilerServices.Extension()>
        Public Function ToBinString(s As String) As String
            Dim messageBytes As Byte() = Text.Encoding.UTF8.GetBytes(s)
            Dim ba As New BitArray(messageBytes)
            Dim sb As New Text.StringBuilder()
            For Each b As Boolean In ba
                sb.Append(CInt(b) And 1)
            Next
            Return sb.ToString()
        End Function

        ''' <summary>
        ''' Возвращает строку, представляющую двоичную последовательность переданного массива битов.
        ''' </summary>
        ''' <param name="bits">Произвольная битовая последовательность.</param>
        <Runtime.CompilerServices.Extension()>
        Public Function ToBinString(bits As IEnumerable(Of Boolean)) As String
            Dim sb As New Text.StringBuilder()
            For Each b As Boolean In bits
                sb.Append(CInt(b) And 1)
            Next
            Return sb.ToString()
        End Function

        ''' <summary>
        ''' Преобразует строку битов в битовую последовательность.
        ''' </summary>
        ''' <param name="binaryString">Строка, составленная из "1" и "0".</param>
        <Runtime.CompilerServices.Extension()>
        Public Function FromBinString(binaryString As String) As List(Of Boolean)
            Dim bits As New List(Of Boolean)
            For Each c As Char In binaryString.ToCharArray()
                bits.Add(Boolean.Parse(c))
            Next
            Return bits
        End Function

        ''' <summary>
        ''' Преобразует битовую последовательность в строку ASCII.
        ''' </summary>
        ''' <param name="bits"></param>
        <Runtime.CompilerServices.Extension()>
        Public Function ToUtf8String(bits As IEnumerable(Of Boolean)) As String
            Dim bytes As New List(Of Byte)
            For i As Integer = 0 To bits.Count - 8 Step 8
                Dim int As Integer = 0
                For j As Integer = 0 To 7
                    int = int Or ((CInt(bits(i + j)) And 1) << j)
                Next
                bytes.Add(CByte(int))
            Next
            Dim s As String = Text.Encoding.UTF8.GetString(bytes.ToArray())
            Return s
        End Function

        ''' <summary>
        ''' Побитово сравнивает 2 массива.
        ''' </summary>
        ''' <param name="ar1"></param>
        ''' <param name="ar2"></param>
        <Runtime.CompilerServices.Extension()>
        Public Function BinaryEquals(ar1 As IEnumerable(Of Boolean), ar2 As IEnumerable(Of Boolean)) As Boolean
            If (ar1.Count <> ar2.Count) Then
                Return False
            End If
            For i As Integer = 0 To ar1.Count - 1
                If (ar1(i) <> ar2(i)) Then
                    Return False
                End If
            Next
            Return True
        End Function

         ''' <summary>
        ''' Добавляет в битовый поток <paramref name="message"/> заданный процент случайных ошибок.
        ''' </summary>
        ''' <param name="message">Исходное сообщение.</param>
        ''' <param name="errorsPercent">Процент ошибок, от 0 до 100.</param>
        Public Function GetMessageWithErrors(message As IEnumerable(Of Boolean), errorsPercent As Integer) As List(Of Boolean)
            Dim numErrors As Integer = CInt(Math.Truncate(message.Count * errorsPercent / 100))
            Dim errorsIndeces As New List(Of Integer)
            Dim rnd As New Random()
            For i As Integer = 0 To numErrors - 1
                Dim r As Integer = rnd.Next(0, message.Count)
                errorsIndeces.Add(r)
            Next
            Dim messageWithErrors As New List(Of Boolean)
            For i As Integer = 0 To message.Count - 1
                If errorsIndeces.Contains(i) Then
                    messageWithErrors.Add(Not message(i))
                Else
                    messageWithErrors.Add(message(i))
                End If
            Next
            Return messageWithErrors
        End Function

    End Module '/Helpers

End Namespace
    

Namespace Viterbi

    ''' <summary>
    ''' Кодер свёрточного кода.
    ''' </summary>
    Public Class Encoder
        Inherits ViterbiBase

#Region "CTOR"

        ''' <summary>
        ''' Конструктор кодера с указанием порождающих многочленов.
        ''' </summary>
        ''' <param name="polynoms">Массив порождающих многочленов (по умолчанию в ВОСЬМЕРИЧНОЙ системе счисления).</param>
        ''' <param name="base">Основание системы счисления, в которой указаны полиномы. Обычно 8 или 10.</param>
        Public Sub New(polynoms() As Integer, Optional base As Integer = 8)
            MyBase.New(polynoms, base)
        End Sub

#End Region '/CTOR

#Region "METHODS"

        ''' <summary>
        ''' Кодирует сообщение <paramref name="message"/>, заданное массивом битов.
        ''' </summary>
        ''' <remarks>
        ''' Пользуясь решёткой, легко проводить кодирование, не высчитывая каждый раз суммы по модулю два. 
        ''' Для этого нужно взять за исходное состояние узел 000 и далее перемещаться по стрелкам в один из двух узлов. 
        ''' Выбор следующего узла определяется кодируемым битом данных: если бит данных «1», то первый слева бит следующего узла должен быть «1», 
        ''' если кодируемый бит «0», то первый слева бит следующего узла должен быть «0». 
        ''' Физически операция перемещения по стрелке соответствует сдвигу в регистре кодера. 
        ''' Выходным значением кодера будут цифры, соответствующие стрелке.
        ''' </remarks>
        Public Function Encode(message As BitArray) As List(Of Boolean)
            Dim encodedMessage As New List(Of Boolean)
            Dim currentNode As Integer = 0 'начинаем с узла "0"
            For stepNum As Integer = 0 To message.Length - 1
                Dim nextTransition As Transition = GetNextTransition(message(stepNum), Transitions(currentNode))
                currentNode = nextTransition.DestinationNode
                encodedMessage.AddRange(nextTransition.CoderOutBits)
            Next
            Return encodedMessage
        End Function

        ''' <summary>
        ''' Кодирует сообщение, заданное строкой символов.
        ''' </summary>
        ''' <param name="message">Сообщение в виде текстовой строки.</param>
        ''' <remarks>Для преобразования в байты применяется кодировка UTF8.</remarks>
        Public Function Encode(message As String) As List(Of Boolean)
            Dim messageBytes As Byte() = Text.Encoding.UTF8.GetBytes(message)
            Dim ba As New BitArray(messageBytes)
            Dim encoded As List(Of Boolean) = Encode(ba)
            Return encoded
        End Function

        ''' <summary>
        ''' Кодирует поток <paramref name="streamToEncode"/> и сохраняет в поток <paramref name="encodedOutputStream"/>.
        ''' </summary>
        ''' <param name="streamToEncode">Двоичный поток, который будет побайтово прочитан и закодирован по алгоритму Витерби.</param>
        ''' <param name="encodedOutputStream">В этот поток (в текстовом!) виде будет сохранён результат.</param>
        Public Sub Encode(streamToEncode As IO.BinaryReader, encodedOutputStream As IO.StreamWriter)
            Do While (streamToEncode.PeekChar <> -1)
                Dim b As Byte = streamToEncode.ReadByte()
                Dim ba As New BitArray({b})
                Dim encodedBits As IEnumerable(Of Boolean) = Encode(ba)
                For Each bit As Boolean In encodedBits
                    encodedOutputStream.Write(CInt(bit) And 1)
                Next
            Loop
        End Sub

        ''' <summary>
        ''' Кодирует сообщение <paramref name="message"/>, заданное массивом битов.
        ''' </summary>
        Public Function Encode(message As IEnumerable(Of Boolean)) As List(Of Boolean)
            Dim b As New BitArray(message.ToArray())
            Return Encode(b)
        End Function

#End Region '/METHODS

    End Class '/Encoder

End Namespace
    

Namespace Viterbi

    ''' <summary>
    ''' Декодер свёрточного кода по алгоритму Витерби.
    ''' </summary>
    Public Class Decoder
        Inherits ViterbiBase

#Region "CTOR"

        ''' <summary>
        ''' Конструктор с указанием порождающих многочленов.
        ''' </summary>
        ''' <param name="polynoms">Массив порождающих многочленов (по умолчанию в ВОСЬМЕРИЧНОЙ системе счисления).</param>
        ''' <param name="base">Основание системы счисления, в которой указаны полиномы. Обычно 8 или 10.</param>
        Public Sub New(polynoms() As Integer, Optional base As Integer = 8)
            MyBase.New(polynoms, base)
        End Sub

#End Region '/CTOR

#Region "METHODS"

        ''' <summary>
        ''' Декодирует битовый поток <paramref name="encodedMessage"/>.
        ''' </summary>
        ''' <param name="encodedMessage"></param>
        Public Function Decode(encodedMessage As IEnumerable(Of Boolean)) As Boolean()
            If (encodedMessage.Count Mod CoderBitness = 0) Then
                Dim paths As New PathHolder(StatesCount)
                'Посимвольно вычитываем из закодированного потока и декодируем:
                For symbol As Integer = 0 To encodedMessage.Count - CoderBitness Step CoderBitness
                    Dim encoderOutput(CoderBitness - 1) As Boolean
                    For bit As Integer = 0 To CoderBitness - 1
                        encoderOutput(bit) = encodedMessage(symbol + bit)
                    Next
                    UpdatePaths(encoderOutput, paths)
                Next
                Dim decodedMessage As Boolean() = ChooseFinalMessage(paths)
                Return decodedMessage
            End If
            Throw New ArgumentException($"Число бит в сообщении ({encodedMessage.Count}) не согласуется с параметрами декодера ({Me.ToString()}).")
        End Function

        ''' <summary>
        ''' Декодирует битовый поток <paramref name="encodedMessage"/>.
        ''' </summary>
        ''' <param name="encodedMessage"></param>
        Public Function Decode(encodedMessage As BitArray) As Boolean()
            Dim bools As New List(Of Boolean)
            For Each b As Boolean In encodedMessage
                bools.Add(b)
            Next
            Return Decode(bools)
        End Function

        ''' <summary>
        ''' Декодирует закодированную строку, состоящую из "1" и "0".
        ''' </summary>
        ''' <param name="binaryString">Строка из битов "1" и "0".</param>
        Public Function Decode(binaryString As String) As List(Of Boolean)
            Dim resBits As New List(Of Boolean)
            For i As Integer = 0 To binaryString.Length - CoderBitness Step CoderBitness
                Dim symbol(CoderBitness - 1) As Boolean
                For j As Integer = 0 To CoderBitness - 1
                    symbol(j) = Integer.Parse(binaryString(i + j)) > 0
                Next
                Dim decoded As Boolean() = Decode(symbol)
                resBits.AddRange(decoded)
            Next
            Return resBits
        End Function

        ''' <summary>
        ''' Декодирует битовый поток, прочитанный из текстового файла битового потока.
        ''' </summary>
        ''' <param name="streamToDecode"></param>
        ''' <param name="decodedOutputStream"></param>
        Public Sub Decode(streamToDecode As IO.TextReader, decodedOutputStream As IO.BinaryWriter)
            Dim byteSymbolLength As Integer = CoderBitness * 8
            Dim ar(0) As Byte
            Do While (streamToDecode.Peek <> -1)

                'Вычитываем по одному закодированному байту (в битах длина закодированного байта = 8 * разрядность_кодера):
                Dim encodedByte(byteSymbolLength - 1) As Boolean
                For i As Integer = 0 To byteSymbolLength - 1
                    Dim ch As Integer = streamToDecode.Read()
                    Dim bitc As Char = ChrW(ch)
                    Dim bit As Integer = Integer.Parse(bitc)
                    encodedByte(i) = CBool(bit)
                Next

                Dim decodedByte As Boolean() = Decode(encodedByte)
                Dim ba As New BitArray(decodedByte)
                ba.CopyTo(ar, 0)
                Dim b As Byte = ar(0)
                decodedOutputStream.Write(b)
            Loop
        End Sub

#End Region '/METHODS

#Region "CLOSED METHODS"

        ''' <summary>
        ''' Восстанавливает сообщение, выбирая его из финальных выживших путей кодера.
        ''' </summary>
        ''' <param name="encoderPaths"></param>
        Private Function ChooseFinalMessage(encoderPaths As PathHolder) As Boolean()
            Dim paths As IEnumerable(Of DecoderPath) = From p As DecoderPath In encoderPaths.Paths
                                                       Where (p.SurvivorPath.Count > 0)
                                                       Select p Order By p.Metrics 'путь с минимальной метрикой окажется вверху списка
            For Each path In paths
                Dim decoded(path.Count - 1) As Boolean
                For i As Integer = 0 To path.Count - 1
                    decoded(i) = path.SurvivorPath(i).DestinationNodeMsb
                Next
                Return decoded 'Если имеется несколько путей с одинаковой минимальной метрикой, выбирается первый, потом выходим из цикла.
            Next
            Return {}
        End Function

        ''' <summary>
        ''' Находит очередные выжившие пути декодера, отбрасывает невыжившие.
        ''' </summary>
        ''' <param name="encoderOut">Очередной символ закодированного сообщения на выходе кодера.</param>
        ''' <param name="paths">Пути декодера. Обновляемое значение.</param>
        Private Sub UpdatePaths(encoderOut As IEnumerable(Of Boolean), ByRef paths As PathHolder)
            Dim currentPaths As Transition() = CalculatePathMetrics(encoderOut, paths)
            Dim survivedPaths As Transition() = SelectSurvivedPaths(currentPaths)
            paths.AddSurvivorPath(survivedPaths)
        End Sub

        ''' <summary>
        ''' Рассчитывает метрики для всех путей.
        ''' </summary>
        ''' <param name="encoderOut">Очередной символ закодированного сообщения на выходе кодера.</param>
        ''' <param name="paths">Вычислитель и селектор путей декодера.</param>
        Private Function CalculatePathMetrics(encoderOut As IEnumerable(Of Boolean), ByRef paths As PathHolder) As Transition()
            Dim transitionsWithMetrics(StatesCount - 1) As Transition
            For i As Integer = 0 To StatesCount - 1
                Dim transCount As Integer = Transitions(i).Count()
                For j As Integer = 0 To transCount - 1
                    Dim trans As Transition = Transitions(i)(j)
                    Dim branchMetric As Integer = CalculateHammingDistance(trans.CoderOutBits, encoderOut)
                    Dim pathMetric As Integer = paths.GetPathMetricByNode(trans.SourceNode)
                    Dim t As Transition = trans.Clone()
                    t.Metrics = branchMetric + pathMetric
                    transitionsWithMetrics(i * transCount + j) = t
                Next
            Next
            Return transitionsWithMetrics
        End Function

        ''' <summary>
        ''' Выбирает и возвращает выжившие пути.
        ''' </summary>
        ''' <remarks>
        ''' Выбирает из 2-х конкурирующих путей, входящих в один узел, путь с минимальной метрикой.
        ''' Также здесь можно просмотреть невыживший путь, если это для чего-то нужно.
        ''' </remarks>
        Private Function SelectSurvivedPaths(currentPaths As Transition()) As Transition()
            Dim survivors(TransitionsCount - 1) As Transition
            For i As Integer = 0 To TransitionsCount - 1
                Dim prevDestNode As Integer = i
                Dim sameDestPaths As IEnumerable(Of Transition) = From t As Transition In currentPaths
                                                                  Where (t.DestinationNode = prevDestNode) Select t 'пути с одним узлом назначения
                Dim minMetricTransition As Transition = sameDestPaths.First() 'примем за минимальную метрику произвольный путь (например, 1-ый)
                For Each t As Transition In sameDestPaths
                    If (t.Metrics < minMetricTransition.Metrics) Then
                        minMetricTransition = t
                    End If
                Next
                survivors(i) = minMetricTransition
            Next
            Return survivors
        End Function

        ''' <summary>
        ''' Рассчитывает Хэмингово расстояние между несколькими битовыми комбинациями.
        ''' </summary>
        ''' <param name="bitCombination">Набор битовых комбинаций. Например, {0,1} и {1,1}. Разрядности комбинаций должны быть одинаковыми.</param>
        ''' <remarks>
        ''' Хэмингово расстояние рассчитывается следующим образом: 
        ''' принятая комбинация складывается по модулю два (ПОРАЗРЯДНО!) со сгенерированной комбинацией и далее рассчитывается количество единиц в получившемся значении. 
        ''' Например, хэмингово расстояние для двух комбинаций 01 и 00 рассчитывается следующим образом: 
        ''' количество единиц (0 xor 0; 1 xor 0) = количество единиц (01) = 1.
        ''' </remarks>
        Private Shared Function CalculateHammingDistance(ParamArray bitCombination() As IEnumerable(Of Boolean)) As Integer
            Dim sumOfOnes As Integer = 0
            For bit As Integer = 0 To bitCombination(0).Count - 1 'поразрядно 
                Dim resultBit As Boolean = False
                For comb As Integer = 0 To bitCombination.Count - 1 'для всех комбинаций
                    resultBit = resultBit Xor bitCombination(comb)(bit) 'считаем сумму по модуля 2
                Next
                If resultBit Then 'если 1, то инкрементируем сумму
                    sumOfOnes += 1
                End If
            Next
            Return sumOfOnes
        End Function

#End Region '/CLOSED METHODS

#Region "NESTED TYPES"

        ''' <summary>
        ''' Содержит полный набор выживших и невыживших путей декодера.
        ''' </summary>
        Private Class PathHolder

            ''' <summary>
            ''' Создаёт объект для хранения путей при декодировании.
            ''' </summary>
            ''' <param name="decoderStatesCount">Число состояний декодера. Число выживших и невыживших путей будет в 2 раза меньше.</param>
            Public Sub New(decoderStatesCount As Integer)
                Dim count As Integer = decoderStatesCount \ 2
                ReDim Paths(count - 1)
                For i As Integer = 0 To count - 1
                    Paths(i) = New DecoderPath()
                Next
            End Sub

#Region "PROPS"

            ''' <summary>
            ''' Массив путей декодера.
            ''' </summary>
            Public ReadOnly Property Paths As DecoderPath()

            ''' <summary>
            ''' Путь уже имеет узлы или ещё нет (флаги для выжившией и невыжевшей ветвей).
            ''' </summary>
            Private IsFirstNode As Boolean() = {True, True}

#End Region '/PROPS

#Region "METHODS"

            ''' <summary>
            ''' Добавляет выживший путь в <see cref="Paths"/>.
            ''' </summary>
            ''' <param name="survivor">Массив выживших переходов.</param>
            Public Sub AddSurvivorPath(ByRef survivor As Transition())
                If IsFirstNode(0) Then
                    AddSurvivorPathFirstly(survivor)
                Else
                    'Новый путь продолжает предыдущий => его начальный узел должен выходить из конечного узла предыдущего узла.
                    'Запоминаем соотвтествие индексов новых выживших уже существующим путям
                    '(если сразу вставлять элемент пути, коллекция Path изменялась бы, что привело бы к ошибкам):
                    Dim survivorIndeces(survivor.Length - 1) As Integer
                    Dim prevPathIndeces As New List(Of Integer)
                    For i As Integer = 0 To survivor.Length - 1
                        survivorIndeces(i) = i
                        For j As Integer = 0 To Paths.Count - 1
                            If (Paths(j).DestinationNode = survivor(i).SourceNode) Then
                                prevPathIndeces.Add(j)
                            End If
                        Next
                    Next

                    'Ключ - индекс текущего пути в Path, значения - новые выжившие пути:
                    Dim pathIndeces As ILookup(Of Integer, Integer) = survivorIndeces.ToLookup(Of Integer, Integer)(
                        Function(key) prevPathIndeces(key),
                        Function(key) key
                        )

                    'Запомним индексы путей, которые можно удалить:
                    Dim survivorsToRemove As New Queue(Of Integer)
                    For i As Integer = 0 To survivorIndeces.Length - 1
                        If (Not pathIndeces.Contains(i)) Then
                            survivorsToRemove.Enqueue(i)
                        End If
                    Next

                    'По сохранённым индексам добавим выжившие пути в Path:
                    For Each survIndeces In pathIndeces
                        Dim pathIndex As Integer = survIndeces.Key

                        'Если по ключу находится 2 узла, 2-ой вставляем по индексу невыжившего пути
                        If (survIndeces.Count > 1) Then
                            Dim survivorToRemove As Integer = survivorsToRemove.Dequeue()
                            Paths(survivorToRemove).SurvivorPath.Clear() 'удаляем невыживший путь
                            For Each node In Paths(pathIndex).SurvivorPath 'копируем текущий путь вместо удалённого
                                Paths(survivorToRemove).AddSurvivorNode(node)
                            Next
                            Paths(survivorToRemove).AddSurvivorNode(survivor(survIndeces(1)))
                        End If

                        '1-ый элемент добавляем как обычно:
                        If (survIndeces.Count >= 1) Then
                            Paths(pathIndex).AddSurvivorNode(survivor(survIndeces(0)))
                        End If
                    Next
                End If
            End Sub

            Private Sub AddSurvivorPathFirstly(ByRef survivors As Transition())
                For i As Integer = 0 To survivors.Length - 1
                    Paths(i).AddSurvivorNode(survivors(i)) 'первый узел добавляем без привязки к предыдущим в произвольный путь (пусть i-ый)
                Next
                IsFirstNode(0) = False
            End Sub

            ''' <summary>
            ''' Возвращает метрику пути по узлу назначения.
            ''' </summary>
            ''' <param name="node">Узел назначения, для пути которого нужна метрика.</param>
            Public Function GetPathMetricByNode(node As Integer) As Integer
                If (Paths(0).SurvivorPath.Count > 0) Then
                    For Each path As DecoderPath In Paths
                        Dim count As Integer = path.SurvivorPath.Count
                        If (path.SurvivorPath(count - 1).DestinationNode = node) Then
                            Return path.Metrics
                        End If
                    Next
                End If
                Return 0
            End Function

#End Region '/METHODS

        End Class '/PathHolder

        ''' <summary>
        ''' Полный путь декодирования.
        ''' </summary>
        Private Class DecoderPath

#Region "PROPS"

            ''' <summary>
            ''' Список выживших переходов при декодировании.
            ''' </summary>
            Public ReadOnly Property SurvivorPath As New List(Of Transition)

            ''' <summary>
            ''' Метрика последнего перехода всего выжившего пути.
            ''' </summary>
            Public ReadOnly Property Metrics As Integer
                Get
                    Return SurvivorPath(SurvivorPath.Count - 1).Metrics
                End Get
            End Property

            ''' <summary>
            ''' Узел назначения последнего перехода всего выжившего пути.
            ''' </summary>
            Public ReadOnly Property DestinationNode As Integer
                Get
                    Return SurvivorPath(SurvivorPath.Count - 1).DestinationNode
                End Get
            End Property

            Public ReadOnly Property Count As Integer
                Get
                    Return SurvivorPath.Count()
                End Get
            End Property

#End Region '/PROPS

#Region "METHODS"

            ''' <summary>
            ''' Добавляет узел к выжившему пути.
            ''' </summary>
            ''' <param name="node"></param>
            Public Sub AddSurvivorNode(node As Transition)
                SurvivorPath.Add(node)
            End Sub

            ''' <summary>
            ''' Возвращает список переходов. В конце - метрика пути.
            ''' </summary>
            Public Overloads Function ToString() As String
                Dim sb As New Text.StringBuilder()
                If (SurvivorPath.Count > 0) Then
                    sb.Append(Convert.ToString(SurvivorPath(0).SourceNode, 2).PadLeft(3, "0"c))
                    sb.Append("; ")
                    For Each t As Transition In SurvivorPath
                        sb.Append(Convert.ToString(t.DestinationNode, 2).PadLeft(3, "0"c))
                        sb.Append("; ")
                    Next
                    sb = sb.Remove(sb.Length - 2, 2)
                End If
                sb.Append($" ({Metrics})")
                Return sb.ToString()
            End Function

#End Region '/METHODS

        End Class '/DecoderPath

#End Region '/NESTED TYPES

    End Class '/Decoder

End Namespace