Bidirekciono stek dekodovanje polarnih kodova
Sažetak
Uvod/cilj: Rad uvodi novi algoritam za dekodovovanje polarnih kodova sa smanjenim kašnjenjem koji je inspirisan bidirekcionim stek dekodovanjem klasičnih konvolucionih kodova, a zasnovan je na tehnici savijanja (eng. folding).
Metode: Stek algoritma (poznat i kao stek pretraga) pogodan je za dekodovanje kodova sa strukturom stabla, dekoder sa listom. Ova tehnika savijanja, koju je uveo Petar Elias, koristi se za smanjivanje kašnjenja algoritama za dekodovanje. Simulacije su rađene primenom postupka Monte Karlo.
Rezultati: Razvijen je novi algoritam za dekodovanje polarnih kodova koji je pogodan za paralelnu implementaciju. Novi algoritam upoređen je sa postojećim, a rezultati simulacije su prikazani.
Zaključak: Polarni kodovi su klasa kodova koja dostiže kapacitet kanala, i usvojena je za kodovanje kontrolnih kanala u 5G novom radiju. Glavni algoritam dekodovanja za polarne kodove jeste sekvencijalni algoritam - tzv. dekoder sa sukcesivnim poništavanjem (eng. Successive cancellation decoding - SCD). Ovaj algoritam ima nisku kompleksnost i odlične performanse u slučaju kodova sa velikom dužinom, ali i vrlo malu pouzdanost na kratkim i srednjim dužinama. Predloženo je nekoliko algoritama za dekodovanje kako bi se poboljšale performanse polarnih kodova. Dekoder sa listom i sukcesivnim poništavanjem (eng. Successive cancellation list decoding - SCLD), zajedno sa cikličkim kodom za proveru grešaka (eng. cyclic redundancy check - CRC), pruža veoma dobre performanse pri ispravljanju grešaka, ali po cenu velike kompleksnosti implementacije. Stek dekoder sa sukcesivnim poništavanjem (eng. Successive cancellation stack decoding - SCSD) pruža slične performanse po pitanju verovatnoće greške pri nižoj kompleksnosti. Pored niske verovatnoće greške, nove aplikacije za rad u kritičnim situacijama zahtevaju i malo kašnjenje, pa je potrebno smanjiti vreme rada dekodera. U radu je predložen novi bidirekcioni algoritam za dekodovanje, koji postiže znatno manje kašnjenje uz približno istu pouzdanost kao i najbolji postojeći algoritmi. Novi algoritam je upoređen sa postojećim algoritmima, a rezultati simulacije su prikazani.
Reference
-3rd Generation Partnership Project. 2016. Final report of 3GPP TSG RAN WG1 #87 v1.0.0. [online]. Available at: https://www.3gpp.org/DynaReport/TDocExMtg--R1-87--31665.htm [Accessed: 1 February 2021].
Alamdar-Yazdi, A. & Kschischang, F.R. 2011. A Simplified Successive-Cancellation Decoder for Polar Codes. IEEE Communications Letters, 15(12), pp. 1378–1380. Available at: https://doi.org/10.1109/LCOMM.2011.101811.111480.
Arikan, E. 2008. A performance comparison of polar codes and Reed-Muller codes. IEEE Communications Letters, 12(6), pp. 447–449. Available at: https://doi.org/10.1109/LCOMM.2008.080017.
Arikan, E. 2009. Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels. IEEE Transactions on Information Theory, 55(7), pp. 3051–3073. Available at: https://doi.org/10.1109/TIT.2009.2021379.
Arikan, E. 2010. Polar codes: A pipelined implementation. In: Proc. 4th Int. Symp. on Broad. Commun. ISBC 2010. pp. 11–14.
Aurora, H., Condo, C. & Gross, W.J. 2018. Low-Complexity Software Stack Decoding of Polar Codes. In: 2018 IEEE International Symposium on Circuits and Systems (ISCAS). pp. 1–5. Available at: https://doi.org/10.1109/ISCAS.2018.8351832.
Aurora, H. & Gross, W.J. 2018. Towards Practical Software Stack Decoding of Polar Codes. [online]. Available at: https://arxiv.org/abs/1809.03606 [Accessed: 1 February 2021].
Balatsoukas-Stimming, A., Parizi, M.B. & Burg, A. 2015. LLR-Based Successive Cancellation List Decoding of Polar Codes. IEEE Transactions on Signal Processing, 63(19), pp. 5165–5179. Available at: https://doi.org/10.1109/TSP.2015.2439211.
Forney, G.D. 2001. Codes on graphs: normal realizations. IEEE Transactions on Information Theory, 47(2), pp. 520–548. Available at: https://doi.org/10.1109/18.910573.
Hanif, M. & Ardakani, M. 2017. Fast Successive-Cancellation Decoding of Polar Codes: Identification and Decoding of New Nodes. IEEE Communications Letters, 21(11), pp. 2360–2363. Available at: https://doi.org/10.1109/LCOMM.2017.2740305.
Hashemi, S.A., Condo, C. & Gross, W.J. 2016. Simplified Successive-Cancellation List decoding of polar codes. In: 2016 IEEE International Symposium on Information Theory (ISIT). pp. 815–819. Available at: https://doi.org/10.1109/ISIT.2016.7541412.
Hashemi, S.A., Mondelli, M., Fazeli, A., Vardy, A., Cioffi, J. & Goldsmith, A. 2020. Parallelism versus Latency in Simplified Successive-Cancellation Decoding of Polar Codes. [online]. Available at: https://arxiv.org/abs/2012.13378 [Accessed: 1 February 2021].
Huang, Y., Zhang, Z., You, X. & Zhang, C. 2018. Efficient Folded SC Polar Line Decoder. In: 2018 IEEE 23rd International Conference on Digital Signal Processing (DSP). pp. 1–5. Available at: https://doi.org/10.1109/ICDSP.2018.8631807.
Kahraman, S., Viterbo, E. & Çelebi, M.E. 2013. Folded tree maximum-likelihood decoder for Kronecker product-based codes. In: 2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 629–636. Available at: https://doi.org/10.1109/Allerton.2013.6736584.
Kahraman, S., Viterbo, E. & Çelebi, M.E. 2014a. Folded successive cancelation decoding of polar codes. In: 2014 Australian Communications Theory Workshop (AusCTW). pp. 57–61. Available at: https://doi.org/10.1109/AusCTW.2014.6766428.
Kahraman, S., Viterbo, E. & Çelebi, M.E. 2014b. Multiple Folding for Successive Cancelation Decoding of Polar Codes. IEEE Wireless Communications Letters, 3(5), pp. 545–548. Available at: https://doi.org/10.1109/LWC.2014.2343970.
Li, B., Shen, H. & Tse, D. 2012. An Adaptive Successive Cancellation List Decoder for Polar Codes with Cyclic Redundancy Check. IEEE Communications Letters, 16(12), pp. 2044–2047. Available at: https://doi.org/10.1109/LCOMM.2012.111612.121898.
Li, B., Shen, H. & Tse, D. 2013. Parallel Decoders of Polar Codes [online]. Available at: https://arxiv.org/abs/1309.1026v1 [Accessed: 1 February 2021].
Li, B., Shen, H., Tse, D. & Tong, W. 2014. Low-latency polar codes via hybrid decoding. In: 2014 8th International Symposium on Turbo Codes and Iterative Information Processing (ISTC). pp. 223–227. Available at: https://doi.org/10.1109/ISTC.2014.6955118.
Niu, K. & Chen, K. 2012b. CRC-Aided Decoding of Polar Codes. IEEE Communications Letters, 16(10), pp. 1668–1671. Available at: https://doi.org/10.1109/LCOMM.2012.090312.121501.
Niu, K. & Chen, K. 2012a. Stack decoding of polar codes. Electronics Letters, 48, pp. 695–697(2). Available at: https://doi.org/10.1049/el.2012.1459.
Sarkis, G., Giard, P., Vardy, A., Thibeault, C. & Gross, W.J. 2014. Fast Polar Decoders: Algorithm and Implementation. IEEE Journal on Selected Areas in Communications, 32(5), pp. 946–957. Available at: https://doi.org/10.1109/JSAC.2014.140514.
Tal, I. & Vardy, A. 2015. List Decoding of Polar Codes. IEEE Transactions on Information Theory, 61(5), pp. 2213–2226. Available at: https://doi.org/10.1109/TIT.2015.2410251.
Vangala, H., Viterbo, E. & Hong, Y. 2014a. Improved multiple folded successive cancellation decoder for polar codes. In: 2014 XXXIth URSI General Assembly and Scientific Symposium (URSI GASS). pp. 1–4. Available at: https://doi.org/10.1109/URSIGASS.2014.6929238.
Vangala, H., Viterbo, E. & Hong, Y. 2014b. A new multiple folded successive cancellation decoder for polar codes. In: 2014 IEEE Information Theory Workshop (ITW 2014). pp. 381–385. Available at: https://doi.org/10.1109/ITW.2014.6970858.
Vangala, H., Viterbo, E. & Hong, Y. 2015. A Comparative Study of Polar Code Constructions for the AWGN Channel. [online]. Available at: https://arxiv.org/abs/1501.02473 [Accessed: 1 February 2021].
Won, J.W. & Ahn, J.M. 2020. 3GPP URLLC patent analysis. ICT Express. Available at: https://doi.org/10.1016/j.icte.2020.09.001.
Xiang, L., Kaykac Egilmez, Z.B., Maunder, R.G. & Hanzo, L. 2019. CRC-Aided Logarithmic Stack Decoding of Polar Codes for Ultra Reliable Low Latency Communication in 3GPP New Radio. IEEE Access, 7, pp. 28559–28573. Available at: https://doi.org/10.1109/ACCESS.2019.2901596.
Xiang, L., Zhong, S., Maunder, R.G. & Hanzo, L. 2020. Reduced-Complexity Low-Latency Logarithmic Successive Cancellation Stack Polar Decoding for 5G New Radio and Its Software Implementation. IEEE Transactions on Vehicular Technology, 69(11), pp. 12449–12458. Available at: https://doi.org/10.1109/TVT.2020.3026915.
Vojnotehnički glasnik omogućava otvoreni pristup i, u skladu sa preporukom CEON-a, primenjuje Creative Commons odredbe o autorskim pravima:
Autori koji objavljuju u Vojnotehničkom glasniku pristaju na sledeće uslove:
- Autori zadržavaju autorska prava i pružaju časopisu pravo prvog objavljivanja rada i licenciraju ga Creative Commons licencom koja omogućava drugima da dele rad uz uslov navođenja autorstva i izvornog objavljivanja u ovom časopisu.
- Autori mogu izraditi zasebne, ugovorne aranžmane za neekskluzivnu distribuciju rada objavljenog u časopisu (npr. postavljanje u institucionalni repozitorijum ili objavljivanje u knjizi), uz navođenje da je rad izvorno objavljen u ovom časopisu.
- Autorima je dozvoljeno i podstiču se da postave objavljeni rad onlajn (npr. u institucionalnom repozitorijumu ili na svojim internet stranicama) pre i tokom postupka prijave priloga, s obzirom da takav postupak može voditi produktivnoj razmeni ideja i ranijoj i većoj citiranosti objavljenog rada (up. Efekat otvorenog pristupa).