---
# System prepended metadata

title: CVSD Final Note

---

# CVSD Final Note

## Videos
Successive-Cancellation (SC) decoder
- [(2) 錯誤控制編碼(16) 極化碼，編碼. Polar code, encoding - YouTube](https://www.youtube.com/watch?v=nxYcZLaPBPo&list=PLu6Wg31FIjYOnEMlVUKhf2sp57Le6zvXY&index=18)
- [(2) 錯誤控制編碼（17）極化碼，SC 解碼；Polar code, SC decoding - YouTube](https://www.youtube.com/watch?v=YD4fF12TVB4&list=PLu6Wg31FIjYOnEMlVUKhf2sp57Le6zvXY&index=18)


Polar codes transform, SC encoding, SC decoding 
(Use tree to illustrate sequence of operations, 只能被一個一個解出來, 使用frozen bit可以跳過)
- [(2) Channel Polarization, Definition of (N,K) Polar Code and Encoding - YouTube](https://www.youtube.com/watch?v=1uYEq4ueOok&list=PLyqSpQzTE6M81HJ26ZaNv0V3ROBrcv-Kc&index=28)
- [(2) Successive Cancellation(SC) Decoder for a General (N,K) Polar Code - YouTube](https://www.youtube.com/watch?v=O3JWkvEY8Lc&list=PLyqSpQzTE6M81HJ26ZaNv0V3ROBrcv-Kc&index=32)

## Background for Basic SC decoder
Use N=4 as an example  

![](https://i.imgur.com/ULtPnzE.png)  

**Function**
- Internal node: step **F**, **G**, **U(Combine)**
- Leaf node: Return decision **u**
![](https://i.imgur.com/UlpMfaM.png)  

**Node operation**
- If not leaf, do the following in sequence
    1. Do step **F** and go to left child
    2. When decision is received from left child, do Step **G** and go to right child
    3. When decision is received from right child, do Step **U(Combine)** and go to parent  

- If leaf, **hard decision** (also can viewed as sign)  


Sequence of Operations, use (K,N)=(10,16) as example
![](https://i.imgur.com/U1emkd4.png)

## Improvement

ref
- [Fast Polar Decoders: Algorithm and Implementations](https://arxiv.org/pdf/1307.7154.pdf)
- [Area-Efficient Partially-Pipelined Architecture for Fast-SSC Decoding of Polar Codes](https://ieeexplore.ieee.org/document/9827219)
- [Multi-mode Unrolled Architectures for Polar Decoders](https://arxiv.org/pdf/1505.01459.pdf)
- **[A Semi-Parallel Successive-Cancellation Decoder for Polar Codes](https://ieeexplore.ieee.org/document/6327689)**
    這篇講蠻仔細的，有列出需要的 alpha-RAM 跟 beta-RAM，PE的數量，計算複雜度與 resource 利用率

Based some observations, some nodes can be merged as a new-node to reduce traversals, following are some conditions to merge, see below example
![](https://i.imgur.com/EbF9NGg.png)

**發生頻率: Rate-0 > Rate-1 > Rep >>> SPC**

| New-node | conditions |
| ------ |--|
| Rate-1 | root of sub-tree whoose leaves are all information bits</br>Output is equal to the **sign of its inputs** (just treat as leaf node)  |
| Rate-0 | root of sub-tree whoose leaves are all frozen bits</br>Output is **0**</br> |
| Rep.   | root of a sub-tree whoose leaves except the last leaf are frozen bits</br>![](https://i.imgur.com/CnApBTc.png) The only information bit gets repeated over N_v output  |
| SPC.   | root of a sub-tree whoose leaves except the first leaf are information bits</br>![](https://i.imgur.com/PRsEFI7.png)|

## Hardware Design

1. output routing for different K
2. node type identification for different K
3. **frozen conditions** 希望可以用數學式表達
    - [Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels](https://ieeexplore.ieee.org/document/5075875)
    - [How to Construct Polar Codes](https://ieeexplore.ieee.org/document/6557004)
    結論: 他們都沒有提到找 frozen bit (排reliability sequence) 的方式，太複雜直接跳過，看來只能 look up 助教提供的 reliability sequence 得知 leaf node 是否 frozen，目前的想法是 non-leaf node 的 node type 可以由該 node 的兩個 children node 的 node-type 求得

Functions need to be implemented by decoder, refer to paper [Fast Polar Decoders: Algorithm and Implementations](https://arxiv.org/pdf/1307.7154.pdf)

![](https://i.imgur.com/xclVkqg.png)

## Idea 

* 用一個sequence存frozen/info
    * 判斷node type
    * 判斷是否輸出
* index -> reliability? K變動就要從頭來過（？
    1. N=128, 256, 512的reliability都寫進去
        * coding方便，不確定繞線cost?
    2. 只用N=512的reliability來判斷frozen/info
        * counter: 對N=128, 256會多花很多cycle，但應該可以平行做
            * N=128: 0~407 (or 0~300)
            * N=256: 0~491 (or 0~443)
            * N=512: 0~511
* reliability -> index? K變動只重新判斷ΔK個、要寫3組

* Storage:
    * if_seq: 512 bits
    * L: total **512 x 12** bits on the path (不包括 input llr storage), input llr 的儲存可以跟 L share，不然就需要 **1024 x 12** bits
    * u: **512 x 1** bits
    * ucap: **512 x 1** bits
    * state table for each node: 1023 internal nodes, use 3 bits to represent a state, need **1023 x 3** bits
    * state
        * L
        * R
        * U
        * Rate-0
        * Rate-1
        * Rep

## Sub-Module

![](https://i.imgur.com/v7oObNP.jpg)

## Progress

### Synthesis
* clk: 6.5 (15-bit without known_K)
    * area: 548939 (worse)
* clk: 6.5 (15-bit with known_K)
    * area: 542650
    * note: timing violation before sending data (@32.5ns), **better A*T**
* clk: 6.0 (15-bit with known_K)
    * area: 598803
    * note: timing violation after sending data (@36ns) (failed?)
* clk: 5.8 (15-bit with known_K)
    * area: 635696
    * note: timing violation before sending data (@5848ps)

* clock gating (remove unknown_K)
    * clk: 6.0
    * area: 481846
    * 8.2840 mW

* clock gating (15-bits remove unknown_k)
    * clk: 6.0
    * area 620435
    * 13.0006 mW

* clock gating (15-bits remove unknown_k)
    * clk: 6.5
    * area 548611
    * 8.68 mW

* clock gating (15-bits remove unknown_k) **better**
    * clk: 7.0
    * area 511365
    * 7.83

### APR
* clk: 6.5ns (15-bit with known_K)
    * area:  775239.92 um^2
    * power: 29.5 mW
    * note:  line 73756 'ANTENNA' is unresolved
             timing violation before sending data (@606ps)
    
* clock gating (15-bits remove known_k)
    * clk:   7.0
    * area:  730873.28 um^2
    * power: 14.7 mW
    * note:  timing violation before sending data (@899ps)

Warning message
![](https://i.imgur.com/yHQN271.jpg)

## Improvement

相較於 baseline 的改動 12/12  
- `polar_deocder.v` if_seq 更新，port 中的 `clear` 訊號拿掉

可以改進的地方
- nodetype判斷 (至少針對baseline pattern優化)
- 存少一點L
- 每層回傳ucap也許不需要 1 cycle/layer
- LLR input排程



