%---------------------------------------------------------------------------------------- % DOCUMENT CONFIGURATIONS %---------------------------------------------------------------------------------------- \documentclass{article} \usepackage{amsmath} \usepackage{amssymb} \title{Information Theory and Coding: Graded Homework} \author{Thaddee Tyl, Benjamin Wesolowski, Aleksandar Markovic, Léonard von Niederhäusern} \begin{document} \maketitle %---------------------------------------------------------------------------------------- % SECTION 1 %---------------------------------------------------------------------------------------- \section{Problem 1} \begin{enumerate} \item[(a)] We have $Q_{i+1} = \sqrt{Z_{i+1}(1- Z_{i+1})}$. With probability $1/2$, $Z_{i+1} = Z_{i}^2$. In this case, we have $$Q_{i+1} = \sqrt{Z_{i}^2\left(1- Z_{i}^2\right)} = \sqrt{Z_{i}^2(1- Z_{i})(1+ Z_{i})} = \sqrt{Q_i^2Z_{i}(1+ Z_{i})}.$$ Therefore, with probability $1/2$, $Q_{i+1} = Q_if_1(Z_i)$ with $f_1(z) = \sqrt{z(1+ z)}$. On the other hand, with probability $1/2$, $Z_{i+1} = 2Z_{i} - Z_{i}^2$. In this case, \begin{alignat*}{1} Q_{i+1} & = \sqrt{\left(2Z_{i} - Z_{i}^2\right)\left(1-2Z_{i} - Z_{i}^2\right)}\\ & = \sqrt{Z_{i}(2 - Z_{i})(1-Z_{i})^2}\\ & = \sqrt{Q_i^2(2 - Z_{i})(1-Z_{i})}. \end{alignat*} So with probability $1/2$, $Q_{i+1} = Q_if_2(Z_i)$ with $f_2(z) = \sqrt{(2-z)(1- z)}$. \item[(b)] Let $\mathfrak F(z) = f_1(z) + f_2(z)$. We have \begin{alignat*}{1} \mathfrak F'(z)& = f_1'(z) + f_2'(z)\\ & = \frac{1 + 2z}{2\sqrt{z(1+z)}} + \frac{-3 + 2z}{2\sqrt{(2-z)(1- z)}}. \end{alignat*} Then, for $0\leq z \leq 1$, we have the following chain \begin{alignat*}{1} \mathfrak F'(z) = 0 & \Leftrightarrow \frac{1 + 2z}{2\sqrt{z(1+z)}} = \frac{3 - 2z}{2\sqrt{(2-z)(1- z)}}\\ & \Leftrightarrow (1 + 2z)\sqrt{(2-z)(1- z)} = (3 - 2z)\sqrt{z(1+z)}\\ & \Leftrightarrow (1 + 2z)\sqrt{(2-z)(1- z)} = (3 - 2z)\sqrt{z(1+z)}\\ & \Rightarrow (1 + 2z)^2(2-z)(1- z) = (3 - 2z)^2z(1+z)\\ & \Leftrightarrow 4 z^4-8 z^3+5 z-3 z^2+2 = 4 z^4-8 z^3-3 z^2+9 z\\ & \Leftrightarrow 2-4 z = 0\\ & \Leftrightarrow z = \frac{1}{2}.\\ \end{alignat*} So if $\mathfrak F$ has an inflexion point on $[0,1]$, it must be at $z = 1/2$. And in fact, we have $\mathfrak F'(1/2) = 0$ so $z = 1/2$ is the unique inflexion point. Moreover, $\mathfrak F(1/2) = \sqrt{3}$, $\mathfrak F(0) = \sqrt{2}$ and $\mathfrak F(1) = \sqrt{2}$. Therefore $\sqrt{3}$ is the maximum of $\mathfrak F$ on $[0,1]$, so for any $0\leq z\leq 1$, $f_1(z) + f_2(z) \leq \sqrt{3}$. Given $Q_0,...,Q_i$, there are only two possible values for $Q_{i+1}$, namely $Q_{i}f_1(Z_i)$ or $Q_{i}f_2(Z_i)$, with equal probability 1/2. So \begin{alignat*}{1} \mathbb E[Q_{i+1}\mid Q_0,...,Q_i] & = \frac{1}{2}Q_{i}f_1(Z_i) + \frac{1}{2}Q_{i}f_2(Z_i)\\ & = Q_{i}\frac{f_1(Z_i) + f_2(Z_i)}{2}\\ & \leq Q_{i}\frac{\sqrt{3}}{2}. \end{alignat*} So for $\rho = \sqrt{3}/2 < 1$, we have $\mathbb E[Q_{i+1}\mid Q_0,...,Q_i] \leq \rho Q_i$. \item[(c)] We use the fact that for any random variables $X$ and $Y$, we have $\mathbb E[Y] = \mathbb E[\mathbb E[Y\mid X]]$. We have \begin{alignat*}{1} \mathbb E[Q_i] & = \mathbb E[\mathbb E[Q_i\mid Q_0,...,Q_{i-1}]]\\ & \leq \mathbb E[ Q_{i-1}] = \rho \mathbb E[ Q_{i-1}]. \end{alignat*} For any $i$, we have $\mathbb E[Q_i] \leq \rho \mathbb E[ Q_{i-1}]$, so $$\mathbb E[Q_i] \leq \rho \mathbb E[ Q_{i-1}] \leq \rho^2 \mathbb E[ Q_{i-2}]\leq ... \leq \rho^i \mathbb E[ Q_{0}] = \rho^i Q_{0}.$$ It remains to see that $Q_{0} \leq 1/2$. We have $Q_0 = \sqrt{z_0(1-z_0)} = f(z_0)$ with $f(z) = \sqrt{z(1-z)}$ for any $0\leq z\leq 1$. Since $f(z)$ is positive, its variation is the same as the variation of $g(z) = f(z)^2 = z(z-1)$. This point is $z = 1/2$ since the derivative of $g$ is $1 - 2z$, which is positive on $[0,1/2]$ (so $f$ is strictly increasing on this interval), zero at $z = 1/2$ and negative on $[1/2,1]$ (so $f$ is strictly decreasing on this interval). So the maximum of $f$ over $[0,1]$ is $f(1/2) = 1/2$. Thus $Q_0 \leq 1/2$, and finally $\mathbb E[Q_i] \leq \rho^i/2$. \item[(d)] We have already observed that $f(z) = \sqrt{z(1-z)}$ is strictly increasing on $[0,1/2]$ and decreasing on $[1/2,1]$. Let $\delta >0$ and $0\leq z\leq 1$. Observe that $f(1-z) = f(z)$. We have the following chain of equivalences~: \begin{alignat*}{1} & z \in (\delta,1-\delta)\\ & \Leftrightarrow z \in (\delta,1/2] \text{ or } z \in [1/2,1-\delta)\\ & \Leftrightarrow \Big(\delta < z \text{ and } z \leq 1/\Big)\text{ or } \Big(\delta < 1- z \text{ and } z \geq 1/2\Big)\\ & \Leftrightarrow \Big(f(\delta) < f(z) \text{ and } z \leq 1/2\Big)\text{ or } \Big(f(\delta) < f(1- z) \text{ and } z \geq 1/2\Big)\\ & \Leftrightarrow \Big(f(\delta) < f(z) \text{ and } z \leq 1/2\Big)\text{ or } \Big(f(\delta) < f(z) \text{ and } z \geq 1/2\Big)\\ & \Leftrightarrow f(\delta) < f(z) \text{ and } \Big(z \leq 1/2 \text{ or } z \geq 1/2\Big)\\ & \Leftrightarrow f(\delta) < f(z)\\ & \Leftrightarrow \sqrt{\delta(1-\delta)} < \sqrt{z(1-z)}\\ \end{alignat*} So $Z_i \in (\delta,1-\delta)$ if and only if $\sqrt{\delta(1-\delta)} < \sqrt{Z_i(1-Z_i)} = Q_i$. Hence, $$\Pr[Z_i \in (\delta,1-\delta)] = \Pr\left[Q_i > \sqrt{\delta(1-\delta)}\right].$$ Let $\Delta = \sqrt{\delta(1-\delta)}$. Let $\Psi$ be the set on possible values for $Q_i$ (the leafs of the complete binary tree of depth $i$). For any $q \in \Psi$, we have $q \geq 0$. Then, \begin{alignat*}{1} \frac{\rho^i}{2} & \geq \mathbb E[Q_i]\\ & = \sum_{q \in \Psi}\Pr[Q_i = q]q\\ & = \sum_{q \in \Psi, q>\Delta}\Pr[Q_i = q]q + \sum_{q \in \Psi, q\leq\Delta}\Pr[Q_i = q]q\\ & \geq \sum_{q \in \Psi, q>\Delta}\Pr[Q_i = q]q\\ & > \Delta\sum_{q \in \Psi, q>\Delta}\Pr[Q_i = q]\\ & = \Delta\Pr\left[Q_i > \Delta\right]. \end{alignat*} Therefore, $$\Pr\left[Q_i > \sqrt{\delta(1-\delta)}\right] \leq \frac{\rho^i}{2\Delta}$$ \end{enumerate} %---------------------------------------------------------------------------------------- % SECTION 2 %---------------------------------------------------------------------------------------- \section{Problem 2} The program used to generate all outputs is annexed at the end of the problem. \begin{enumerate} \item[(a)] We consider sending 93 bits of information in a 256 bit codeword over a Binary Erasure Channel of erasure probability 0.5. Here is a list of the erasure probabilities of the 93 channels indexed with the most + signs, from lowest probability to highest. \begin{verbatim} === Erasure probability of 93 indexes with the most + signs === 8.63616855509e-78 5.87747175411e-39 1.17549435082e-38 4.7019774011e-38 7.52270468004e-37 1.86661826955e-34 4.56978021156e-30 1.05340571681e-23 2.16840434497e-19 4.33680868893e-19 8.67361737383e-19 1.73467053702e-18 3.46934107082e-18 1.38765173149e-17 2.73248478097e-17 5.46496954173e-17 1.01822021309e-16 2.18572203402e-16 3.38997155009e-15 4.27540885136e-15 8.55081730736e-15 3.41885641353e-14 5.1596510308e-13 6.49124245982e-12 1.29824615309e-11 5.15738358148e-11 5.17906768993e-11 7.1664454612e-10 1.86264514771e-09 3.72523345006e-09 7.45023952991e-09 1.47850864067e-08 1.48995696692e-08 2.01813795645e-08 2.95683750091e-08 4.03587048974e-08 4.2535764885e-08 5.9129560222e-08 1.16446921002e-07 1.58238966417e-07 1.84941250311e-07 2.32837655963e-07 3.69802962745e-07 7.3928799619e-07 9.02969231596e-07 1.43661370237e-06 1.71294406327e-06 2.87079380532e-06 5.17057292798e-06 7.20622363062e-06 1.08382114784e-05 1.43629336054e-05 1.43930961484e-05 2.8649041195e-05 2.87091243111e-05 4.20453270169e-05 5.35397183974e-05 0.000103461370162 0.000106527550912 0.000369949678325 0.000401749162798 0.000412441475489 0.000699613221793 0.000795426995731 0.00081316308667 0.00111524982725 0.0015595932285 0.00257726025404 0.00261587683531 0.00454260819389 0.0050474979966 0.00866700356933 0.0115422674676 0.0129264282943 0.0140407666464 0.016075396351 0.0229107716046 0.023890426144 0.0562551115958 0.0656754629179 0.069250936743 0.110285476109 0.139319270069 0.184930397406 0.204204154472 0.237502176403 0.342645714418 0.360164755053 0.491653163968 0.550356457917 0.653612313433 0.789499296844 0.88228091295 \end{verbatim} \item[(b)] This time, we consider the 93 channels that have the smallest erasure probabilities. They are listed below, sorted from lowest probability to highest, along with their indices. Noteworthy are the probabilities associated with the 93rd channel, 0.0380982022567, and the 94th channel, 0.0522007921375. \begin{verbatim} === 94 smallest erasure probabilities and their indices === 255 8.63616855509e-78 254 5.87747175411e-39 253 1.17549435082e-38 251 4.7019774011e-38 247 7.52270468004e-37 239 1.86661826955e-34 223 4.56978021156e-30 191 1.05340571681e-23 252 2.16840434497e-19 250 4.33680868893e-19 249 8.67361737383e-19 246 1.73467053702e-18 245 3.46934107082e-18 243 1.38765173149e-17 238 2.73248478097e-17 237 5.46496954173e-17 127 1.01822021309e-16 235 2.18572203402e-16 231 3.38997155009e-15 222 4.27540885136e-15 221 8.55081730736e-15 219 3.41885641353e-14 215 5.1596510308e-13 190 6.49124245982e-12 189 1.29824615309e-11 207 5.15738358148e-11 187 5.17906768993e-11 183 7.1664454612e-10 248 1.86264514771e-09 244 3.72523345006e-09 242 7.45023952991e-09 236 1.47850864067e-08 241 1.48995696692e-08 126 2.01813795645e-08 234 2.95683750091e-08 125 4.03587048974e-08 175 4.2535764885e-08 233 5.9129560222e-08 230 1.16446921002e-07 123 1.58238966417e-07 220 1.84941250311e-07 229 2.32837655963e-07 218 3.69802962745e-07 217 7.3928799619e-07 227 9.02969231596e-07 214 1.43661370237e-06 119 1.71294406327e-06 213 2.87079380532e-06 159 5.17057292798e-06 188 7.20622363062e-06 211 1.08382114784e-05 206 1.43629336054e-05 186 1.43930961484e-05 205 2.8649041195e-05 185 2.87091243111e-05 111 4.20453270169e-05 182 5.35397183974e-05 203 0.000103461370162 181 0.000106527550912 240 0.000244112687312 179 0.000369949678325 124 0.000401749162798 174 0.000412441475489 232 0.00048627228099 199 0.000699613221793 122 0.000795426995731 173 0.00081316308667 228 0.000964832250228 95 0.00111524982725 121 0.0015595932285 216 0.00171889787861 226 0.00189959089458 171 0.00257726025404 118 0.00261587683531 212 0.00338581261149 225 0.00368472116212 158 0.00454260819389 117 0.0050474979966 210 0.00657344959462 157 0.00866700356933 204 0.0106763107803 184 0.0106874701036 167 0.0115422674676 209 0.0124238377326 110 0.0129264282943 115 0.0140407666464 63 0.016075396351 202 0.0202397311189 180 0.0205359094091 155 0.0229107716046 109 0.023890426144 201 0.0366864481777 178 0.0380982022567 198 0.0522007921375 \end{verbatim} \item[(c)] The sum of all erasure probabilities that method a yields is 5.26906295371, while that of erasure probabilities of method b is 0.351933744493. Clearly, taking the channels with the most + signs does not yield the best channels. Listed below are the indices of the channels used by method a and b. \begin{verbatim} === Indices in use by method a === 31 47 55 59 61 62 63 79 87 91 93 94 95 103 107 109 110 111 115 117 118 119 121 122 123 124 125 126 127 143 151 155 157 158 159 167 171 173 174 175 179 181 182 183 185 186 187 188 189 190 191 199 203 205 206 207 211 213 214 215 217 218 219 220 221 222 223 227 229 230 231 233 234 235 236 237 238 239 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 === Indices in use by method b === 63 95 109 110 111 115 117 118 119 121 122 123 124 125 126 127 155 157 158 159 167 171 173 174 175 178 179 180 181 182 183 184 185 186 187 188 189 190 191 198 199 201 202 203 204 205 206 207 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 \end{verbatim} The following python code was used to output the results discussed above. \begin{verbatim} # Exercise a # Compute the erasure probability of W+ after one step of the polar transform, # starting from BEC(bep). # bep: binary erasure probability def erasureProbPlus(bep): return bep * bep # Compute the erasure probability of W- after one step of the polar transform, # starting from BEC(bep). # bep: binary erasure probability def erasureProbMinus(bep): return 2 * bep - bep * bep class ArikanChannels: def __init__(self, bep, times): self.bep = bep # Binary erasure probability self.times = times # Number of polar transforms # We use a dictionary where the keys are a string of + and - signs. self.channelsBySign, self.channels = polarTransform(bep, times) self.channelsByErasureProb = \ byErasureProbability(self.channelsBySign, self.channels) def polarTransform(bep, steps): firstLevel = {'': bep} indexedLevel = [bep] for i in range(steps): firstLevel, indexedLevel = nextPolarStep(firstLevel, indexedLevel) return (firstLevel, indexedLevel) def nextPolarStep(prevLevel, prevIndexedLevel): nextLevel = {} indexedLevel = [] for signs in prevLevel: nextLevel[signs + '-'] = erasureProbMinus(prevLevel[signs]) nextLevel[signs + '+'] = erasureProbPlus(prevLevel[signs]) for channel in prevIndexedLevel: indexedLevel.append(erasureProbMinus(channel)) indexedLevel.append(erasureProbPlus(channel)) return (nextLevel, indexedLevel) # Get a map from erasure probabilities to a list [index, sign]. def byErasureProbability(bySign, byIndex): map = {} for index, channel in enumerate(byIndex): map[channel] = [index] for sign in bySign: map[bySign[sign]].append(sign) return map # Number of plus signs in the string of signs. def plusSigns(signs): count = 0 for s in signs: if s == '+': count += 1 return count # Return the channels with `n` plus signs. def channelsWithNPlusSigns(channels, n): beps = [] for signs in channels.channelsBySign: if plusSigns(signs) == n: beps.append(channels.channelsBySign[signs]) return beps # Return a list of lists of channels, from the channels with the most number # of + signs, to channels with the least number of + signs. def groupedChannels(channels): channelGroups = [] for nPlusSigns in range(channels.times + 1): group = channelsWithNPlusSigns(channels, nPlusSigns) channelGroups.append(group) channelGroups.reverse() return channelGroups # Return the `n` binary erasure channels with the most + signs. def mostPosChannels(channels, n): channelGroups = groupedChannels(channels) # We can flatten channelGroups. ordChannels = [bep for group in channelGroups for bep in group] return ordChannels[:n] # Go through 8 polar transformations, erasure prob. 0.5. channels = ArikanChannels(0.5, 8) # Take the 93 channels with the most +. theMostPosChannels = mostPosChannels(channels, 93) theMostPosChannels.sort() print "\n=== Erasure probability of 93 indexes with the most + signs ===" for channel in theMostPosChannels: print channel # Exercise b # Return a list of `n` 2-uples with the `n` binary erasure channels of # smallest erasure probability, and their index. def smallestErasureChannels(channels, n): smallest = [] for index, channel in enumerate(channels.channels): smallest.append((channel, index)) smallest.sort() return smallest[:n] print "\n=== 94 smallest erasure probabilities and their indices ===" smallest94ErasureChannels = smallestErasureChannels(channels, 94) for channel, index in smallest94ErasureChannels: print index, '\t', channel # Exercise c def add(a, b): return a + b print "\n=== Sum of erasure probabilities for method a ===" print reduce(add, theMostPosChannels) print "\n=== Sum of erasure probabilities for method b ===" print reduce(add, [a for a, b in smallest94ErasureChannels]) print "\n=== Indices in use by method a ===" def indexFromErasureProbability(bep): return channels.channelsByErasureProb[bep][0] theMostPosIndices = map(indexFromErasureProbability, theMostPosChannels) theMostPosIndices.sort() for index in theMostPosIndices: print index print "\n=== Indices in use by method b ===" smallest94ErasureIndices = map(indexFromErasureProbability, [a for a, b in smallest94ErasureChannels]) smallest94ErasureIndices.sort() for index in smallest94ErasureIndices: print index \end{verbatim} \end{enumerate} %---------------------------------------------------------------------------------------- % SECTION 3 %---------------------------------------------------------------------------------------- \section{Problem 3} Here is the source code: \begin{verbatim} # Problem 3 of the graded homework # W is our BSC channel with error probability e # l is the level of our polarization # s is the exponenent of W in {+,-}^l # + is represented by a 1, - by a 0 # n=2^l F=GF(2) # Z/2Z, simple way to represent bits eps=0.11 def choose_y(e,u=F(0)): # Choose y according to W(y|u) if u==0: D=GeneralDiscreteDistribution([1-eps,eps]) else: D=GeneralDiscreteDistribution([eps,1-eps]) return F(D.get_random_element()) def create_Y(l,e,u=F(0)): # Create the vector y^n according to W(y|u) if l==1: return [choose_y(e,u),choose_y(e,u)] return [create_Y(l-1,e,u),create_Y(l-1,e,u)] def create_U(l,a=F(0)): # Create the vector u^n with full a's (1 or 0) u=[a,a] for i in xrange(l-1): u=[u,u] return u def add_U(u,v=F(1)): # Add two vectors, if v=1, then it will simply invert u if u==0 or u==1: return u+v if v==1: return [add_U(u[0],v),add_U(u[1],v)] return [add_U(u[0],v[0]),add_U(u[1],v[1])] def channels(l): # List all channels in a binary representation r=[] for i in xrange(1<>1] # find the last +/- if s0==0: return (1/2)*( Ws(e,s,y[0],u[0])*Ws(e,s,y[1],create_U(l)) + Ws(e,s,y[0],add_U(u[0]))*Ws(e,s,y[1],create_U(l,F(1))) ) else: return (1/2)*Ws(e,s,y[0],u[1])*Ws(e,s,y[1],u[1]) def WL(l,e): # compute the max likelihood and say whether the chosen bit is right or not S=channels(l) y=create_Y(l,e) u=create_U(l) v=create_U(l,F(1)) c=[] for i in xrange(1<b: r=F(0) elif a