Polar codes for distributed source coding

Abstract

Kutupsal kodlar, ikili-girişli ayrık hafızasız kanalların kapasitesine ulaşan ve düşük kodlama ve kod çözme karmaşıklığına sahip ilk kodlar olarak Arıkan tarafindan keşfedilmişlerdir. Kutupsal kodların temel prensibi olan `kutuplaşma hadisesi`, hem tekli hem de çoklu kullanıcılı kurgularda farklı kanal ve kaynak problemlerine uygulanabilmektedir. Bu çalışmada, çoklu kullanıcılı dağıtık kaynak kodlama problemleri için kutupsal kodlama metodları incelenmektedir. İlk olarak, aynı zamanda Slepian-Wolf problemi olarak da bilinen dağıtık kaynak kodlama probleminin kısıtlı bir hali ele alınmaktadır. Bu kısıt, ilişkili kaynakların dağılımı üzerinedir. Kaynakların `ikili simetrik` olduğu durumda tek kullanıcılı kutupsal kodlar kullanılarak tüm kapasite alanına zaman paylaşımsız erişilebildiği gösterilmektedir. Daha sonra, genel kaynak dağılımlarına sahip Slepian-Wolf problemini çözmek için kullanılan ikili kullanıcılı kutupsal kodlama metodu ele alınmaktadır. Ayrıca bu metod, Slepian-Wolf probleminin eşleniği olan çoklu erişimli kanal problemini de içerecek şekilde genişletilmektedir.Daha sonra, dağıtık kurgulara sahip iki farklı kayıplı kaynak kodlama problemi incelenmektedir. Ele alınan ilk problem, Slepian-Wolf probleminin kayıplı hali olan kayıplı dağıtık kaynak kodlama problemidir. Bu problemin kapasite bölgesi genel olarak bilinmese de Berger-Tung iç sınırı olarak bilinen iyi bir iç sınır bulunmaktadır. Berger-Tung bölgesinin tümüne erişen bir kutupsal kodlama yöntemi tasarlanmaktadır. Ele alınan ikinci problem, çoklu tanım kodlaması problemidir. Bu problemin de genel kapasite alanı bilinmemektedir. El Gamal-Cover iç sınırı, bu problem için bilinen en iyi sınırdır. El Gamal-Cover kapasite sınırındaki herhangi bir noktaya erişebilen bir kutupsal kodlama yöntemi geliştirilmektedir.

Polar codes were invented by Arıkan as the first `capacity achieving` codes for binary-input discrete memoryless symmetric channels with low encoding and decoding complexity. The `polarization phenomenon`, which is the underlying principle of polar codes, can be applied to different source and channel coding problems both in single-user and multi-user settings. In this work, polar coding methods for multi-user distributed source coding problems are investigated. First, a restricted version of lossless distributed source coding problem, which is also referred to as the Slepian-Wolf problem, is considered. The restriction is on the distribution of correlated sources. It is shown that if the sources are `binary symmetric` then single-user polar codes can be used to achieve full capacity region without time sharing. Then, a method for two-user polar coding is considered which is used to solve the Slepian-Wolf problem with arbitrary source distributions. This method is also extended to cover multiple-access channel problem which is the dual of Slepian-Wolf problem.Next, two lossy source coding problems in distributed settings are investigated. The first problem is the distributed lossy source coding which is the lossy version of the Slepian-Wolf problem. Although the capacity region of this problem is not known in general, there is a good inner bound called the Berger-Tung inner bound. A polar coding method that can achieve the whole dominant face of the Berger-Tung region is devised. The second problem considered is the multiple description coding problem. The capacity region for this problem is also not known in general. El Gamal-Cover inner bound is the best known bound for this problem. A polar coding method that can achieve any point on the dominant face of El Gamal-Cover region is devised.