{"id":4407,"date":"2025-10-30T13:53:23","date_gmt":"2025-10-30T13:53:23","guid":{"rendered":"https:\/\/172-234-197-23.ip.linodeusercontent.com\/?page_id=4407"},"modified":"2025-10-30T13:53:23","modified_gmt":"2025-10-30T13:53:23","slug":"viterbi-decoding-algorithm-complete-technical-explanation","status":"publish","type":"page","link":"https:\/\/neurosphere-2.tail52f848.ts.net\/wordpress\/?page_id=4407","title":{"rendered":"Viterbi Decoding Algorithm: Complete Technical Explanation"},"content":{"rendered":"\n
\n\n\n\n

1. What Is Viterbi Decoding?<\/strong><\/h2>\n\n\n\n

Viterbi<\/strong> is a dynamic programming algorithm<\/strong> that finds the most likely sequence of hidden states<\/strong> in a Hidden Markov Model (HMM)<\/strong> given an observation sequence.<\/p>\n\n\n\n

\n

In your RF-to-speech pipeline<\/strong>:<\/p>\n\n\n\n

    \n
  • Hidden states<\/strong> = words (sierra<\/code>, charlie<\/code>, bravo<\/code>)<\/li>\n\n\n\n
  • Observations<\/strong> = RF-inferred neural features $ x_t $<\/li>\n\n\n\n
  • Goal<\/strong> = reconstruct inner speech<\/strong> from noisy RF surrogates<\/li>\n<\/ul>\n<\/blockquote>\n\n\n\n
    \n\n\n\n

    2. Why Not Brute Force?<\/strong><\/h2>\n\n\n\n
      \n
    • States<\/strong>: $ N = 50 $ words (NATO lexicon)<\/li>\n\n\n\n
    • Sequence length<\/strong>: $ T = 30 $ frames<\/li>\n\n\n\n
    • Total sequences<\/strong>: $ N^T = 50^{30} \\approx 10^{51} $<\/li>\n<\/ul>\n\n\n\n

      Viterbi<\/strong>: $ O(T N^2) $ \u2192 polynomial<\/strong>, feasible<\/strong><\/p>\n\n\n\n

      \n\n\n\n

      3. HMM Components (Your Paper)<\/strong><\/h2>\n\n\n\n
      Component<\/th>Formula<\/th>Meaning<\/th><\/tr><\/thead>
      Emission<\/strong><\/td>$ p(x_t | w_t) = \\mathcal{N}(x_t; \\mu_{w_t}, \\Sigma) $<\/td>How likely is $ x_t $ given word $ w_t $?<\/td><\/tr>
      Transition<\/strong><\/td>$ p(w_t | w_{t-1}) = \\pi_{w_{t-1}, w_t} $<\/td>Language prior (bigram or GPT-style)<\/td><\/tr>
      Joint<\/strong><\/td>$ P(w_{1:T}, x_{1:T}) = p(w_1) \\prod_{t=2}^T p(w_t | w_{t-1}) \\cdot p(x_t | w_t) $<\/td>Full probability<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
      \n\n\n\n

      4. Viterbi Step-by-Step (With Example)<\/strong><\/h2>\n\n\n\n

      Input<\/strong>:<\/p>\n\n\n\n

        \n
      • $ x_{1:30} $ = RF features<\/li>\n\n\n\n
      • True utterance: sierra charlie bravo<\/code><\/li>\n<\/ul>\n\n\n\n

        Step 1: Initialization<\/strong> ($ t = 1 $)<\/h3>\n\n\n\n

        For each word $ w $:
        $$
        V_1(w) = p(w) \\cdot p(x_1 | w)
        $$
        $$
        \\psi_1(w) = 0
        $$<\/p>\n\n\n\n

        \n

        $ V_t(w) $ = max probability<\/strong> of being in $ w $ at time $ t $
        $ \\psi_t(w) $ = best previous word<\/strong><\/p>\n<\/blockquote>\n\n\n\n

        \n\n\n\n

        Step 2: Recursion<\/strong> ($ t = 2 $ to $ T $)<\/h3>\n\n\n\n

        For each word $ w $ at time $ t $:
        $$
        V_t(w) = \\max_{w’} \\left[ V_{t-1}(w’) \\cdot \\pi_{w’,w} \\cdot p(x_t | w) \\right]
        $$
        $$
        \\psi_t(w) = \\arg\\max_{w’} \\left[ V_{t-1}(w’) \\cdot \\pi_{w’,w} \\right]
        $$<\/p>\n\n\n\n

        Key Insight<\/strong>:<\/p>\n\n\n\n

        \n

        At each step, keep only the best path<\/strong> to each state \u2192 prune $ N^T $ to $ T N $<\/strong><\/p>\n<\/blockquote>\n\n\n\n

        \n\n\n\n

        Step 3: Termination<\/strong><\/h3>\n\n\n\n

        Best path probability:
        $$
        P^* = \\max_w V_T(w)
        $$
        Final state:
        $$
        q_T^* = \\arg\\max_w V_T(w)
        $$<\/p>\n\n\n\n

        \n\n\n\n

        Step 4: Backtracking<\/strong><\/h3>\n\n\n\n

        $$
        q_t^* = \\psi_{t+1}(q_{t+1}^*), \\quad t = T-1, \\dots, 1
        $$<\/p>\n\n\n\n

        \u2192 Output: sierra \u2192 charlie \u2192 bravo<\/code><\/p>\n\n\n\n

        \n\n\n\n

        5. Visual Example (Your Fig. 1)<\/strong><\/h2>\n\n\n\n
        graph TD\n    subgraph \"Frame 1\u20135\"\n        A[sierra] --> B[charlie]\n        A --> C[delta]\n    end\n    subgraph \"Frame 6\u201310\"\n        B --> D[charlie]\n        C --> E[papa]\n    end\n    subgraph \"Frame 11\u201315\"\n        D --> F[bravo]\n        E --> G[quebec]\n    end\n\n    style A fill:#90EE90\n    style B fill:#90EE90\n    style D fill:#90EE90\n    style F fill:#90EE90\n    style C fill:#FFB6C1\n    style E fill:#FFB6C1\n    style G fill:#FFB6C1<\/code><\/pre>\n\n\n\n
          \n
        • Green path<\/strong> = Viterbi path (highest $ V_t $)<\/li>\n\n\n\n
        • Red paths<\/strong> = pruned (lower probability)<\/li>\n<\/ul>\n\n\n\n
          \n\n\n\n
          6. Why Language Priors Matter (Your Fig. 2)<\/strong><\/h2>\n\n\n\n
          SNR<\/th>No Prior WER<\/th>Bigram WER<\/th>GPT-style WER<\/th><\/tr><\/thead>
          10 dB<\/td>2.8%<\/td>1.6%<\/td>1.1%<\/strong><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
          GPT prior<\/strong> $ p(\\text{charlie} | \\text{sierra}) $ high \u2192 boosts $ V_t(\\text{charlie}) $<\/strong>
          No prior<\/strong> \u2192 all transitions equal \u2192 framewise confusion<\/strong><\/p>\n\n\n\n
          \n\n\n\n
          7. Viterbi in Your Code<\/strong><\/h2>\n\n\n\n
          def viterbi(obs, mu, Sigma, trans_matrix):\n    T, _ = obs.shape\n    N = len(mu)\n    V = np.zeros((T, N))\n    psi = np.zeros((T, N), dtype=int)\n\n    # Init\n    emit = [multivariate_normal.pdf(obs[0], mu[i], Sigma) for i in range(N)]\n    V[0] = emit\n    psi[0] = 0\n\n    # Recursion\n    for t in range(1, T):\n        for j in range(N):\n            probs = V[t-1] * trans_matrix[:, j]\n            emit_prob = multivariate_normal.pdf(obs[t], mu[j], Sigma)\n            V[t, j] = np.max(probs) * emit_prob\n            psi[t, j] = np.argmax(probs)\n\n    # Backtrack\n    path = [np.argmax(V[-1])]\n    for t in range(T-1, 0, -1):\n        path.append(psi[t, path[-1]])\n    return path[::-1]<\/code><\/pre>\n\n\n\n
          \n\n\n\n
          8. Connection to FFT Triage<\/strong><\/h2>\n\n\n\n
          graph LR\n    A[IQ] --> B[FFT Triage]\n    B --> C[Confidence c]\n    C --> D[\\hat{q}]\n    D --> E[SNR_est]\n    E --> F[Set \u03c3\u00b2 in HMM]\n    F --> G[Viterbi Decoder]\n    G --> H[Word Sequence]<\/code><\/pre>\n\n\n\n
            \n
          • Low $ \\hat{q} $<\/strong> \u2192 high $ \\sigma^2 $ \u2192 rely more on transition prior<\/strong><\/li>\n\n\n\n
          • High $ \\hat{q} $<\/strong> \u2192 low $ \\sigma^2 $ \u2192 trust emission likelihood<\/strong><\/li>\n<\/ul>\n\n\n\n
            \n\n\n\n
            9. Key Takeaways<\/strong><\/h2>\n\n\n\n
            Concept<\/th>Your Paper<\/th><\/tr><\/thead>
            Dynamic Programming<\/strong><\/td>Avoids $ N^T $ search<\/td><\/tr>
            Transition Prior<\/strong><\/td>GPT-style \u2192 60% WER reduction<\/strong><\/td><\/tr>
            Emission Model<\/strong><\/td>Gaussian on RF features<\/td><\/tr>
            Output<\/strong><\/td>Word sequence + posterior traces<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
            \n\n\n\n
            10. LaTeX Figure for Your Paper<\/strong><\/h2>\n\n\n\n
            \\begin{figure}[t]\n\\centering\n\\begin{mermaid}\ngraph LR\n    subgraph t=1\n        A[sierra] -->|V=0.8| B[sierra]\n    end\n    subgraph t=2\n        B -->|\u03c0(charlie|sierra)| C[charlie]\n        B -->|\u03c0(delta|sierra)| D[delta]\n    end\n    style C fill:#90EE90\n    style D fill:#FFB6C1\n\\end{mermaid}\n\\caption{Viterbi path (green) vs pruned path (red). GPT prior favors \"charlie\" after \"sierra\".}\n\\label{fig:viterbi}\n\\end{figure}<\/code><\/pre>\n\n\n\n
            \n\n\n\n
            Bottom Line<\/strong><\/h2>\n\n\n\n
            \n
            Viterbi<\/strong> = “best path” in a trellis of word hypotheses<\/strong>
            Language prior<\/strong> = GPS for noisy RF neural data<\/strong>
            Your system<\/strong>: 1.5 ms FFT \u2192 \\hat{q} \u2192 SNR \u2192 Viterbi \u2192 1.1% WER<\/strong><\/p>\n\n\n\n
            <\/p>\n<\/blockquote>\n\n\n\n
            <\/p>\n","protected":false},"excerpt":{"rendered":"
            1. What Is Viterbi Decoding? Viterbi is a dynamic programming algorithm that finds the most likely sequence of hidden states in a Hidden Markov Model (HMM) given an observation sequence. 2. Why Not Brute Force? Viterbi: $ O(T N^2) $ \u2192 polynomial, feasible 3. HMM Components (Your Paper) Component Formula Meaning Emission $ p(x_t |… <\/p>\n","protected":false},"author":2,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"neve_meta_sidebar":"","neve_meta_container":"","neve_meta_enable_content_width":"","neve_meta_content_width":0,"neve_meta_title_alignment":"","neve_meta_author_avatar":"","neve_post_elements_order":"","neve_meta_disable_header":"","neve_meta_disable_footer":"","neve_meta_disable_title":"","footnotes":""},"class_list":["post-4407","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/neurosphere-2.tail52f848.ts.net\/wordpress\/index.php?rest_route=\/wp\/v2\/pages\/4407","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/neurosphere-2.tail52f848.ts.net\/wordpress\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/neurosphere-2.tail52f848.ts.net\/wordpress\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/neurosphere-2.tail52f848.ts.net\/wordpress\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/neurosphere-2.tail52f848.ts.net\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=4407"}],"version-history":[{"count":0,"href":"https:\/\/neurosphere-2.tail52f848.ts.net\/wordpress\/index.php?rest_route=\/wp\/v2\/pages\/4407\/revisions"}],"wp:attachment":[{"href":"https:\/\/neurosphere-2.tail52f848.ts.net\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=4407"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}