1••••(1/2)[6]•

3+ +1=0

•

0

•
0•
•

(2/2)
•••••
•

[1]

-k+1••(n, k)(Singleton bound)

•• n•

kdmin

n-k+1+1•

BCHBCH
[7]

•
•2

•

BCH

•
•

•

BCH
(Bose Chaudhuri Hocquenghem)3

Golay• Golay• Golay
•
•

12324

• BCH
•
• 2

Golay
3

11

[3]url

•

12

Golay

• hIp://math.shinshu-u.ac.jp/~hanaki/script/BinaryGolay.html

LDPC• LDPC(Low-Density Parity Check)•••••• c=110 001 111• LDPC0m=1 0 1• hIp://www.kumikomi.net/interface/sample/201210/if10_157.pdf

LDPC• TurboproductsPropagaYon)•[4]k bits
n bitsr = k/n•
••••
•

[17]
LDPC
sumBN (BayesianNetwork)
BP(Beliefm bits

•
•k
• XOR
• CRC
• hIp://sakaiyas.cocolog-ni]y.com/nikki/2010/03/ldcp-staircase-.html
• URL

•
•

1
• 1
•

1
•
•
•
•

→→•
•

•

•

•

[8]

••

•

1960

Turbo• Turbo•[9] LDPC•••••• Turbo2••
•

[7]••
•••
•

•
[20]

• SpaYo-temporal vector-coding (STVC)[18]• Discrete Matrix MulYtone•

Discrete Matrix

MulYtone (DMMT)
[19]

••

MIMON-(1/3)••••• hIp://news.mynavi.jp/arYcles/2009/06/01/idt_mimo/002.html• URLAlamouY(2/3)
••

•
••

•

[21]

•
•

(3/3)
•[22]

•
Distributed Space-Time Coding•(Linear Dispersion Code)

[22]
[23]

•
•
[24]

••
•
•

LT Codes[10]•• LT Codes
•

••
1.
2.
3. dd
ExOR

Raptor Codes[11-13]• Rapter Codes• LT Codes•

2006

LT CodesRaptor Codes
LT-Codes•• Raptor Codes• LDPC

Pre-coding

Pre-coding• hIp://www.merl.com/publicaYons/docs/TR2004-037.pdf
MITSUBISHI ELECTRIC RESERCH LABORATORIES RatelessCodes on Noisy Channels
LTCodes Raptor Codes BER•

Raptor Codes

BER

Strider[14]• Strider••••

Strider

Spinal Codes[15, 16]• Spinal Codes• Spinal Codes•• AWGN•••••

Spinal Codes

SNR
SNR

• ハミング符号• ブロック符号– BCH 符号（ランダム誤り） [1]– Golay 符号（ランダム誤り） [2, 3]– LDPC 符号（ランダム誤り） [4]∗ LDGM 符号 (派生？)– ファイヤ符号（バースト誤り） [5]– リードソロモン符号（バースト誤り） [6, 7]• 畳み込み符号– しきい値復号（ランダム誤り）– ビタビ復号（ランダム誤り） [8]– 逐次復号（ランダム誤り）– ターボ符号（ランダム誤り） [4, 7, 9]∗ SOVA 復号∗ MAP 復号
• 連接符号– BCH 符号＋リードソロモン符号– 畳み込み符号＋リードソロモン符号• レートレス符号– LT 符号 [10]– Raptor 符号 [11–13]– strider 符号 [14]– spinal 符号 [15, 16]

参考文献[1] Yingquan Wu. New list decoding algorithms for reed-solomon and bchcodes. In Information Theory, 2007. ISIT 2007. IEEE International
Symposium on, pp. 2806–2810, June 2007.
[2] Vera Pless. On the uniqueness of the golay codes. Journal of Combinatorial theory, Vol. 5, No. 3, pp. 215–228, 1968.
[3] 笠原祥一, 横尾英俊. ゴーレイ符号による情報ハイディングと画像デー
タへの応用. 電子情報通信学会論文誌 A, Vol. 91, No. 6, pp. 685–694,2008.
[4] 松嶋敏泰. ターボ符号，ldpc 符号の復号アルゴリズム. ベイジアンネッ
トチュートリアル, 2001.
[5] 博一岡野. マイクロコンピュータによる fire 符号の高速復号法. 情報処
理学会論文誌, Vol. 21, No. 5, pp. 375–382, sep 1980.
[6] Omar Aitsab and Ramesh Pyndiah. Performance of reed-solomon blockturbo code. In Global Telecommunications Conference, 1996. GLOBECOM ’96. ’Communications: The Key to Global Prosperity, Vol. 1, pp.
121–125 vol.1, Nov 1996.
[7] 西村芳一（編）. 改訂新版 データの符号化技術と誤り訂正の基礎. CQ出版社, 2011.

[8] 安田豊. ヴィタビ復号による誤り訂正方式の研究. PhD thesis, 京都大学,1984.
[9] Claude. Berrou, Alain. Glavieux, and Punya. Thitimajshima. Nearshannon limit error-correcting coding and decoding: Turbo-codes. 1. InCommunications, 1993. ICC ’93 Geneva. Technical Program, Conference Record, IEEE International Conference on, Vol. 2, pp. 1064–1070
vol.2, May 1993.
[10] M. Luby. Lt codes. In Foundations of Computer Science, 2002. Proceedings. The 43rd Annual IEEE Symposium on, pp. 271–280, 2002.
[11] Amin. Shokrollahi. Raptor codes. Information Theory, IEEE Transactions on, Vol. 52, No. 6, pp. 2551–2567, June 2006.
[12] Omid Etesami and Amin Shokrollahi. Raptor codes on binary memoryless symmetric channels. IEEE TRANSACTIONS ON INFORMATION THEORY, Vol. 522006, No. 5, pp. 2033–2051, 2006.

[13] Auguste Venkiah, Charly Poulliat, and David Declercq. Jointly decoded raptor codes: Analysis and design for the BIAWGN channel.
EURASIP J. Wirel. Commun. Netw., Vol. 2009, pp. 16:1–16:11, 2009.
[14] Aditya Gudipati and Sachin Katti. Strider: Automatic rate adaptationand collision handling. In Proceedings of the ACM SIGCOMM 2011
Conference, SIGCOMM ’11, pp. 158–169, New York, NY, USA, 2011.
ACM.
[15] Jonathan Perry, Hari Balakrishnan, and Devavrat Shah. Rateless spinalcodes. In Proceedings of the 10th ACM Workshop on Hot Topics in
Networks, HotNets-X, pp. 6:1–6:6, New York, NY, USA, 2011. ACM.
[16] Jonathan Perry, Peter Iannucci, Kermin Elliott Fleming, Hari Balakrishnan, and Devavrat Shah. Spinal Codes. In ACM SIGCOMM,Helsinki, Finland, August 2012.
[17] 笠井健太. 多元 ldpc 符号とその応用. 電子情報通信学会技術研究報告,
pp. 1–6, 宮城県, 9 月 2010.
[18] Gregory G. Raleigh and John M. Cioﬃ. Spatio-temporal coding for
wireless communication. Communications, IEEE Transactions on,Vol. 46, No. 3, pp. 357–366, Mar 1998.
[19] Ayman.F. Naguib,

Vahid Tarokh,

Nambirajan. Seshadri,andA.Robert. Calderbank. A space-time coding modem for high-data-rate
wireless communications. Selected Areas in Communications, IEEE
Journal on, Vol. 16, No. 8, pp. 1459–1478, Oct 1998.
[20] F. Schreckenbach, N. Görtz, J. Hagenauer, and G. Bauch. Optimizedsymbol mappings for bit-interleaved coded modulation with iterative
decoding. IEEE Commun. Lett, Vol. 7, pp. 593–595, 2003.
[21] Vahid Tarokh, Hamid Jafarkhani, and A.Robert. Calderbank. Spacetime block coding for wireless communications: performance results.
Selected Areas in Communications, IEEE Journal on, Vol. 17, No. 3,
pp. 451–460, Mar 1999.
[22] Yindi Jing and Babak Hassibi. Distributed space-time coding in wireless relay networks. Wireless Communications, IEEE Transactions on,Vol. 5, No. 12, pp. 3524–3536, December 2006.
[23] Babak. Hassibi and Bertrand M. Hochwald. High-rate codes that arelinear in space and time. Information Theory, IEEE Transactions on,Vol. 48, No. 7, pp. 1804–1824, Jul 2002.

[24] Andrej. Stefanov and Elza. Erkip. Cooperative coding for wirelessnetworks. Communications, IEEE Transactions on, Vol. 52, No. 9, pp.
1470–1476, Sept 2004.