Exercises#
Hill, Raymond. (1986). A First Course in Coding Theory. Oxford University Press: Oxford Applied Mathematics and Computing Science Series.
Table of Contents#
Programming Environment#
Show code cell source
# %load imports.py
import numpy as np
import pandas as pd
import matplotlib as mpl
from matplotlib.patches import Rectangle
import matplotlib.pyplot as plt
plt.style.use('ggplot');
plt.rcParams.update({'text.usetex' : True});
%matplotlib inline
from collections import defaultdict
from itertools import combinations,product
import itertools
from typing import Set
from IPython.display import display, Math
from datetime import datetime as d
import locale as l
import platform as p
import sys as s
pad = 20
print(f"{'Executed'.upper():<{pad}}: {d.now()}")
print()
print(f"{'Platform' :<{pad}}: "
f"{p.mac_ver()[0]} | "
f"{p.system()} | "
f"{p.release()} | "
f"{p.machine()}")
print(f"{'' :<{pad}}: {l.getpreferredencoding()}")
print()
print(f"{'Python' :<{pad}}: {s.version}")
print(f"{'' :<{pad}}: {s.version_info}")
print(f"{'' :<{pad}}: {p.python_implementation()}")
print()
print(f"{'Matplotlib' :<{pad}}: {mpl.__version__}")
print(f"{'NumPy' :<{pad}}: {np .__version__}")
#==================================================
def rc (q : int,
n : int) -> Set[str]:
"""Repetition Code
Generate a q-ary repetition block code of length n.
"""
S=set()
for i in range(q):
S.add(str(i)*n)
return S
def fqn (q : int,
n : int,
g : int = 0) -> Set[str]:
"""Construct a linear space of dimension n over a finite field of order q.
Parameters
==========
g : If the space is very large, opt for the first g elements of a generator object.
"""
if bool(g):
f=itertools.product(range(q),repeat=n)
return set(''.join(str(i) for i in next(f)) for _ in range(g))
else:
return {''.join(str(bit) for bit in word) for word in itertools.product(range(q),repeat=n)}
def qarycode_to_nbitstring (code={'3121','2101'},k=4):
"""Convert a q-ary code """
for n in code:
print(' '.join(format(int(i),f'0{k}b') for i in n))
def hd (a : str = '1001',
b : str = '0101') -> int:
"""HAMMING DISTANCE
Parameters
==========
x : str
y : str
Return
======
int
"""
assert len(a) == len(b), 'x and y must have the same length'
return sum(x!=y for x,y in zip(a,b))
def nbfmd (c : Set[str],
pr : bool = False) -> np.float16:
"""NAIVE BRUTE FORCE MINIMUM DISTANCE d(C)
Computes the pairwise Hamming distance for all codewords and returns the minimum value.
This is a naive (i.e., non vectorized) implementation using nested for loops.
Parameters
==========
c : code
pr : Print intermediate steps.
Returns
=======
d(C)
"""
# convert a set of string vectors to a 2D NumPy array of integers
c=np.array([list(codeword) for codeword in c],dtype=np.float16)
# intialize empty hamming distance matrix
hamming = np.empty([c.shape[0]]*2,dtype=np.float16)
for i,x in enumerate(c):
for j,y in enumerate(c):
hamming[i,j]=(x!=y).sum()
# the diagonal represents the Hamming distance of a codeword with itself, which is always 0.
np.fill_diagonal(hamming,np.inf)
if pr == True:
print(hamming)
return hamming.min().astype(np.int8)
def one_error_detecting (q : int,
code : Set[str],
p : bool = False) -> bool:
"""Verify that a code is one-error detecting.
No one-bit error equals a codeword.
"""
flag=True
alphabet=set(str(i) for i in range(q))
for codeword in code:
if p:
print()
print(f"{'orig cw : ':10}{codeword}")
for i in range(len(codeword)):
a,b,c=codeword[:i],codeword[i],codeword[i+1:]
symbols=alphabet-set(codeword[i])
for symbol in symbols:
cw=codeword[:i]+symbol+codeword[i+1:] # SINGLE ERROR
if cw in code:
flag=False
if p:
print(f"{'ERROR':10}{cw}")
else:
if p:
print(f"{'':10}{cw}")
return flag
# set(''.join(l for l in i) for i in itertools.product('10',repeat=3))
# set(''.join(l for l in i) for i in itertools.combinations_with_replacement('012',r=3))
# set(''.join(l for l in i) for i in itertools.combinations('01',r=2))
EXECUTED : 2024-05-21 15:46:26.839695
Platform : 14.4.1 | Darwin | 23.4.0 | arm64
: UTF-8
Python : 3.11.9 | packaged by conda-forge | (main, Apr 19 2024, 18:34:54) [Clang 16.0.6 ]
: sys.version_info(major=3, minor=11, micro=9, releaselevel='final', serial=0)
: CPython
Matplotlib : 3.8.4
NumPy : 1.26.4
1#
[1.1]#
If the following message were received from outer space, why might it be conjectured that it was sent by a race of human-like beings who have one arm twice as long as the other?
[Hint: The number of digits in the message is the product of two prime numbers.]
message='00110000011000111111110110010011001001100101111000100100010010001001001100110'
message
'00110000011000111111110110010011001001100101111000100100010010001001001100110'
len(message)
77
c=np.array(list(message)).reshape(11,7)
c
array([['0', '0', '1', '1', '0', '0', '0'],
['0', '0', '1', '1', '0', '0', '0'],
['1', '1', '1', '1', '1', '1', '1'],
['1', '0', '1', '1', '0', '0', '1'],
['0', '0', '1', '1', '0', '0', '1'],
['0', '0', '1', '1', '0', '0', '1'],
['0', '1', '1', '1', '1', '0', '0'],
['0', '1', '0', '0', '1', '0', '0'],
['0', '1', '0', '0', '1', '0', '0'],
['0', '1', '0', '0', '1', '0', '0'],
['1', '1', '0', '0', '1', '1', '0']], dtype='<U1')
print(np.array([[''.join(row)] for row in np.array(list(message)).reshape(11,7)]))
fig = plt.figure(figsize=(6,6));
ax = plt.subplot();
for i,row in enumerate(c):
for j,col in enumerate(row):
#print(i,j,col)
if int(col):
ax.add_patch(Rectangle((j,i),1,1,facecolor='blue'));
ax.set_aspect(1);
ax.set_xticks(ticks=np.arange(0,c.shape[1]+1));
ax.set_yticks(ticks=np.arange(0,c.shape[0]+1));
ax.set_xlim(0,c.shape[1]);
ax.set_ylim(c.shape[0],0);
[['0011000']
['0011000']
['1111111']
['1011001']
['0011001']
['0011001']
['0111100']
['0100100']
['0100100']
['0100100']
['1100110']]
Error in callback <function _draw_all_if_interactive at 0x153fa2200> (for post_execute), with arguments args (),kwargs {}:
---------------------------------------------------------------------------
PermissionError Traceback (most recent call last)
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/pyplot.py:197, in _draw_all_if_interactive()
195 def _draw_all_if_interactive() -> None:
196 if matplotlib.is_interactive():
--> 197 draw_all()
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/_pylab_helpers.py:132, in Gcf.draw_all(cls, force)
130 for manager in cls.get_all_fig_managers():
131 if force or manager.canvas.figure.stale:
--> 132 manager.canvas.draw_idle()
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/backend_bases.py:1893, in FigureCanvasBase.draw_idle(self, *args, **kwargs)
1891 if not self._is_idle_drawing:
1892 with self._idle_draw_cntx():
-> 1893 self.draw(*args, **kwargs)
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/backends/backend_agg.py:388, in FigureCanvasAgg.draw(self)
385 # Acquire a lock on the shared font cache.
386 with (self.toolbar._wait_cursor_for_draw_cm() if self.toolbar
387 else nullcontext()):
--> 388 self.figure.draw(self.renderer)
389 # A GUI class may be need to update a window using this draw, so
390 # don't forget to call the superclass.
391 super().draw()
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/artist.py:95, in _finalize_rasterization.<locals>.draw_wrapper(artist, renderer, *args, **kwargs)
93 @wraps(draw)
94 def draw_wrapper(artist, renderer, *args, **kwargs):
---> 95 result = draw(artist, renderer, *args, **kwargs)
96 if renderer._rasterizing:
97 renderer.stop_rasterizing()
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/artist.py:72, in allow_rasterization.<locals>.draw_wrapper(artist, renderer)
69 if artist.get_agg_filter() is not None:
70 renderer.start_filter()
---> 72 return draw(artist, renderer)
73 finally:
74 if artist.get_agg_filter() is not None:
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/figure.py:3154, in Figure.draw(self, renderer)
3151 # ValueError can occur when resizing a window.
3153 self.patch.draw(renderer)
-> 3154 mimage._draw_list_compositing_images(
3155 renderer, self, artists, self.suppressComposite)
3157 for sfig in self.subfigs:
3158 sfig.draw(renderer)
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/image.py:132, in _draw_list_compositing_images(renderer, parent, artists, suppress_composite)
130 if not_composite or not has_images:
131 for a in artists:
--> 132 a.draw(renderer)
133 else:
134 # Composite any adjacent images together
135 image_group = []
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/artist.py:72, in allow_rasterization.<locals>.draw_wrapper(artist, renderer)
69 if artist.get_agg_filter() is not None:
70 renderer.start_filter()
---> 72 return draw(artist, renderer)
73 finally:
74 if artist.get_agg_filter() is not None:
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/axes/_base.py:3070, in _AxesBase.draw(self, renderer)
3067 if artists_rasterized:
3068 _draw_rasterized(self.figure, artists_rasterized, renderer)
-> 3070 mimage._draw_list_compositing_images(
3071 renderer, self, artists, self.figure.suppressComposite)
3073 renderer.close_group('axes')
3074 self.stale = False
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/image.py:132, in _draw_list_compositing_images(renderer, parent, artists, suppress_composite)
130 if not_composite or not has_images:
131 for a in artists:
--> 132 a.draw(renderer)
133 else:
134 # Composite any adjacent images together
135 image_group = []
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/artist.py:72, in allow_rasterization.<locals>.draw_wrapper(artist, renderer)
69 if artist.get_agg_filter() is not None:
70 renderer.start_filter()
---> 72 return draw(artist, renderer)
73 finally:
74 if artist.get_agg_filter() is not None:
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/axis.py:1388, in Axis.draw(self, renderer, *args, **kwargs)
1385 renderer.open_group(__name__, gid=self.get_gid())
1387 ticks_to_draw = self._update_ticks()
-> 1388 tlb1, tlb2 = self._get_ticklabel_bboxes(ticks_to_draw, renderer)
1390 for tick in ticks_to_draw:
1391 tick.draw(renderer)
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/axis.py:1315, in Axis._get_ticklabel_bboxes(self, ticks, renderer)
1313 if renderer is None:
1314 renderer = self.figure._get_renderer()
-> 1315 return ([tick.label1.get_window_extent(renderer)
1316 for tick in ticks if tick.label1.get_visible()],
1317 [tick.label2.get_window_extent(renderer)
1318 for tick in ticks if tick.label2.get_visible()])
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/axis.py:1315, in <listcomp>(.0)
1313 if renderer is None:
1314 renderer = self.figure._get_renderer()
-> 1315 return ([tick.label1.get_window_extent(renderer)
1316 for tick in ticks if tick.label1.get_visible()],
1317 [tick.label2.get_window_extent(renderer)
1318 for tick in ticks if tick.label2.get_visible()])
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/text.py:956, in Text.get_window_extent(self, renderer, dpi)
951 raise RuntimeError(
952 "Cannot get window extent of text w/o renderer. You likely "
953 "want to call 'figure.draw_without_rendering()' first.")
955 with cbook._setattr_cm(self.figure, dpi=dpi):
--> 956 bbox, info, descent = self._get_layout(self._renderer)
957 x, y = self.get_unitless_position()
958 x, y = self.get_transform().transform((x, y))
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/text.py:373, in Text._get_layout(self, renderer)
370 ys = []
372 # Full vertical extent of font, including ascenders and descenders:
--> 373 _, lp_h, lp_d = _get_text_metrics_with_cache(
374 renderer, "lp", self._fontproperties,
375 ismath="TeX" if self.get_usetex() else False, dpi=self.figure.dpi)
376 min_dy = (lp_h - lp_d) * self._linespacing
378 for i, line in enumerate(lines):
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/text.py:69, in _get_text_metrics_with_cache(renderer, text, fontprop, ismath, dpi)
66 """Call ``renderer.get_text_width_height_descent``, caching the results."""
67 # Cached based on a copy of fontprop so that later in-place mutations of
68 # the passed-in argument do not mess up the cache.
---> 69 return _get_text_metrics_with_cache_impl(
70 weakref.ref(renderer), text, fontprop.copy(), ismath, dpi)
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/text.py:77, in _get_text_metrics_with_cache_impl(renderer_ref, text, fontprop, ismath, dpi)
73 @functools.lru_cache(4096)
74 def _get_text_metrics_with_cache_impl(
75 renderer_ref, text, fontprop, ismath, dpi):
76 # dpi is unused, but participates in cache invalidation (via the renderer).
---> 77 return renderer_ref().get_text_width_height_descent(text, fontprop, ismath)
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/backends/backend_agg.py:213, in RendererAgg.get_text_width_height_descent(self, s, prop, ismath)
211 _api.check_in_list(["TeX", True, False], ismath=ismath)
212 if ismath == "TeX":
--> 213 return super().get_text_width_height_descent(s, prop, ismath)
215 if ismath:
216 ox, oy, width, height, descent, font_image = \
217 self.mathtext_parser.parse(s, self.dpi, prop)
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/backend_bases.py:652, in RendererBase.get_text_width_height_descent(self, s, prop, ismath)
648 fontsize = prop.get_size_in_points()
650 if ismath == 'TeX':
651 # todo: handle properties
--> 652 return self.get_texmanager().get_text_width_height_descent(
653 s, fontsize, renderer=self)
655 dpi = self.points_to_pixels(72)
656 if ismath:
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/texmanager.py:366, in TexManager.get_text_width_height_descent(cls, tex, fontsize, renderer)
364 dpi_fraction = renderer.points_to_pixels(1.) if renderer else 1
365 with dviread.Dvi(dvifile, 72 * dpi_fraction) as dvi:
--> 366 page, = dvi
367 # A total height (including the descent) needs to be returned.
368 return page.width, page.height + page.descent, page.descent
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/dviread.py:296, in Dvi.__iter__(self)
280 def __iter__(self):
281 """
282 Iterate through the pages of the file.
283
(...)
294 integers.
295 """
--> 296 while self._read():
297 yield self._output()
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/dviread.py:375, in Dvi._read(self)
373 while True:
374 byte = self.file.read(1)[0]
--> 375 self._dtable[byte](self, byte)
376 name = self._dtable[byte].__name__
377 if name == "_push":
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/dviread.py:227, in _dispatch.<locals>.decorate.<locals>.wrapper(self, byte)
225 if state is not None and self.state != state:
226 raise ValueError("state precondition failed")
--> 227 return method(self, *[f(self, byte-min) for f in get_args])
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/dviread.py:526, in Dvi._fnt_def(self, k, c, s, d, a, l)
524 @_dispatch(min=243, max=246, args=('olen1', 'u4', 'u4', 'u4', 'u1', 'u1'))
525 def _fnt_def(self, k, c, s, d, a, l):
--> 526 self._fnt_def_real(k, c, s, d, a, l)
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/dviread.py:531, in Dvi._fnt_def_real(self, k, c, s, d, a, l)
529 n = self.file.read(a + l)
530 fontname = n[-l:].decode('ascii')
--> 531 tfm = _tfmfile(fontname)
532 if c != 0 and tfm.checksum != 0 and c != tfm.checksum:
533 raise ValueError('tfm checksum mismatch: %s' % n)
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/dviread.py:1116, in _fontfile(cls, suffix, texname)
1114 @lru_cache
1115 def _fontfile(cls, suffix, texname):
-> 1116 return cls(find_tex_file(texname + suffix))
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/dviread.py:1082, in find_tex_file(filename)
1079 filename = filename.decode('utf-8', errors='replace')
1081 try:
-> 1082 lk = _LuatexKpsewhich()
1083 except FileNotFoundError:
1084 lk = None # Fallback to directly calling kpsewhich, as below.
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/dviread.py:1037, in _LuatexKpsewhich.__new__(cls)
1034 @lru_cache # A singleton.
1035 def __new__(cls):
1036 self = object.__new__(cls)
-> 1037 self._proc = self._new_proc()
1038 return self
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/dviread.py:1041, in _LuatexKpsewhich._new_proc(self)
1040 def _new_proc(self):
-> 1041 return subprocess.Popen(
1042 ["luatex", "--luaonly",
1043 str(cbook._get_data_path("kpsewhich.lua"))],
1044 stdin=subprocess.PIPE, stdout=subprocess.PIPE)
File ~/anaconda3/envs/ml/lib/python3.11/subprocess.py:1026, in Popen.__init__(self, args, bufsize, executable, stdin, stdout, stderr, preexec_fn, close_fds, shell, cwd, env, universal_newlines, startupinfo, creationflags, restore_signals, start_new_session, pass_fds, user, group, extra_groups, encoding, errors, text, umask, pipesize, process_group)
1022 if self.text_mode:
1023 self.stderr = io.TextIOWrapper(self.stderr,
1024 encoding=encoding, errors=errors)
-> 1026 self._execute_child(args, executable, preexec_fn, close_fds,
1027 pass_fds, cwd, env,
1028 startupinfo, creationflags, shell,
1029 p2cread, p2cwrite,
1030 c2pread, c2pwrite,
1031 errread, errwrite,
1032 restore_signals,
1033 gid, gids, uid, umask,
1034 start_new_session, process_group)
1035 except:
1036 # Cleanup if the child failed starting.
1037 for f in filter(None, (self.stdin, self.stdout, self.stderr)):
File ~/anaconda3/envs/ml/lib/python3.11/subprocess.py:1955, in Popen._execute_child(self, args, executable, preexec_fn, close_fds, pass_fds, cwd, env, startupinfo, creationflags, shell, p2cread, p2cwrite, c2pread, c2pwrite, errread, errwrite, restore_signals, gid, gids, uid, umask, start_new_session, process_group)
1953 err_msg = os.strerror(errno_num)
1954 if err_filename is not None:
-> 1955 raise child_exception_type(errno_num, err_msg, err_filename)
1956 else:
1957 raise child_exception_type(errno_num, err_msg)
PermissionError: [Errno 13] Permission denied: 'luatex'
---------------------------------------------------------------------------
PermissionError Traceback (most recent call last)
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/IPython/core/formatters.py:343, in BaseFormatter.__call__(self, obj)
341 pass
342 else:
--> 343 return printer(obj)
344 # Finally look for special method names
345 method = get_real_method(obj, self.print_method)
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/IPython/core/pylabtools.py:152, in print_figure(fig, fmt, bbox_inches, base64, **kwargs)
149 from matplotlib.backend_bases import FigureCanvasBase
150 FigureCanvasBase(fig)
--> 152 fig.canvas.print_figure(bytes_io, **kw)
153 data = bytes_io.getvalue()
154 if fmt == 'svg':
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/backend_bases.py:2164, in FigureCanvasBase.print_figure(self, filename, dpi, facecolor, edgecolor, orientation, format, bbox_inches, pad_inches, bbox_extra_artists, backend, **kwargs)
2161 # we do this instead of `self.figure.draw_without_rendering`
2162 # so that we can inject the orientation
2163 with getattr(renderer, "_draw_disabled", nullcontext)():
-> 2164 self.figure.draw(renderer)
2165 if bbox_inches:
2166 if bbox_inches == "tight":
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/artist.py:95, in _finalize_rasterization.<locals>.draw_wrapper(artist, renderer, *args, **kwargs)
93 @wraps(draw)
94 def draw_wrapper(artist, renderer, *args, **kwargs):
---> 95 result = draw(artist, renderer, *args, **kwargs)
96 if renderer._rasterizing:
97 renderer.stop_rasterizing()
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/artist.py:72, in allow_rasterization.<locals>.draw_wrapper(artist, renderer)
69 if artist.get_agg_filter() is not None:
70 renderer.start_filter()
---> 72 return draw(artist, renderer)
73 finally:
74 if artist.get_agg_filter() is not None:
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/figure.py:3154, in Figure.draw(self, renderer)
3151 # ValueError can occur when resizing a window.
3153 self.patch.draw(renderer)
-> 3154 mimage._draw_list_compositing_images(
3155 renderer, self, artists, self.suppressComposite)
3157 for sfig in self.subfigs:
3158 sfig.draw(renderer)
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/image.py:132, in _draw_list_compositing_images(renderer, parent, artists, suppress_composite)
130 if not_composite or not has_images:
131 for a in artists:
--> 132 a.draw(renderer)
133 else:
134 # Composite any adjacent images together
135 image_group = []
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/artist.py:72, in allow_rasterization.<locals>.draw_wrapper(artist, renderer)
69 if artist.get_agg_filter() is not None:
70 renderer.start_filter()
---> 72 return draw(artist, renderer)
73 finally:
74 if artist.get_agg_filter() is not None:
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/axes/_base.py:3070, in _AxesBase.draw(self, renderer)
3067 if artists_rasterized:
3068 _draw_rasterized(self.figure, artists_rasterized, renderer)
-> 3070 mimage._draw_list_compositing_images(
3071 renderer, self, artists, self.figure.suppressComposite)
3073 renderer.close_group('axes')
3074 self.stale = False
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/image.py:132, in _draw_list_compositing_images(renderer, parent, artists, suppress_composite)
130 if not_composite or not has_images:
131 for a in artists:
--> 132 a.draw(renderer)
133 else:
134 # Composite any adjacent images together
135 image_group = []
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/artist.py:72, in allow_rasterization.<locals>.draw_wrapper(artist, renderer)
69 if artist.get_agg_filter() is not None:
70 renderer.start_filter()
---> 72 return draw(artist, renderer)
73 finally:
74 if artist.get_agg_filter() is not None:
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/axis.py:1388, in Axis.draw(self, renderer, *args, **kwargs)
1385 renderer.open_group(__name__, gid=self.get_gid())
1387 ticks_to_draw = self._update_ticks()
-> 1388 tlb1, tlb2 = self._get_ticklabel_bboxes(ticks_to_draw, renderer)
1390 for tick in ticks_to_draw:
1391 tick.draw(renderer)
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/axis.py:1315, in Axis._get_ticklabel_bboxes(self, ticks, renderer)
1313 if renderer is None:
1314 renderer = self.figure._get_renderer()
-> 1315 return ([tick.label1.get_window_extent(renderer)
1316 for tick in ticks if tick.label1.get_visible()],
1317 [tick.label2.get_window_extent(renderer)
1318 for tick in ticks if tick.label2.get_visible()])
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/axis.py:1315, in <listcomp>(.0)
1313 if renderer is None:
1314 renderer = self.figure._get_renderer()
-> 1315 return ([tick.label1.get_window_extent(renderer)
1316 for tick in ticks if tick.label1.get_visible()],
1317 [tick.label2.get_window_extent(renderer)
1318 for tick in ticks if tick.label2.get_visible()])
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/text.py:956, in Text.get_window_extent(self, renderer, dpi)
951 raise RuntimeError(
952 "Cannot get window extent of text w/o renderer. You likely "
953 "want to call 'figure.draw_without_rendering()' first.")
955 with cbook._setattr_cm(self.figure, dpi=dpi):
--> 956 bbox, info, descent = self._get_layout(self._renderer)
957 x, y = self.get_unitless_position()
958 x, y = self.get_transform().transform((x, y))
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/text.py:373, in Text._get_layout(self, renderer)
370 ys = []
372 # Full vertical extent of font, including ascenders and descenders:
--> 373 _, lp_h, lp_d = _get_text_metrics_with_cache(
374 renderer, "lp", self._fontproperties,
375 ismath="TeX" if self.get_usetex() else False, dpi=self.figure.dpi)
376 min_dy = (lp_h - lp_d) * self._linespacing
378 for i, line in enumerate(lines):
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/text.py:69, in _get_text_metrics_with_cache(renderer, text, fontprop, ismath, dpi)
66 """Call ``renderer.get_text_width_height_descent``, caching the results."""
67 # Cached based on a copy of fontprop so that later in-place mutations of
68 # the passed-in argument do not mess up the cache.
---> 69 return _get_text_metrics_with_cache_impl(
70 weakref.ref(renderer), text, fontprop.copy(), ismath, dpi)
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/text.py:77, in _get_text_metrics_with_cache_impl(renderer_ref, text, fontprop, ismath, dpi)
73 @functools.lru_cache(4096)
74 def _get_text_metrics_with_cache_impl(
75 renderer_ref, text, fontprop, ismath, dpi):
76 # dpi is unused, but participates in cache invalidation (via the renderer).
---> 77 return renderer_ref().get_text_width_height_descent(text, fontprop, ismath)
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/backends/backend_agg.py:213, in RendererAgg.get_text_width_height_descent(self, s, prop, ismath)
211 _api.check_in_list(["TeX", True, False], ismath=ismath)
212 if ismath == "TeX":
--> 213 return super().get_text_width_height_descent(s, prop, ismath)
215 if ismath:
216 ox, oy, width, height, descent, font_image = \
217 self.mathtext_parser.parse(s, self.dpi, prop)
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/backend_bases.py:652, in RendererBase.get_text_width_height_descent(self, s, prop, ismath)
648 fontsize = prop.get_size_in_points()
650 if ismath == 'TeX':
651 # todo: handle properties
--> 652 return self.get_texmanager().get_text_width_height_descent(
653 s, fontsize, renderer=self)
655 dpi = self.points_to_pixels(72)
656 if ismath:
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/texmanager.py:366, in TexManager.get_text_width_height_descent(cls, tex, fontsize, renderer)
364 dpi_fraction = renderer.points_to_pixels(1.) if renderer else 1
365 with dviread.Dvi(dvifile, 72 * dpi_fraction) as dvi:
--> 366 page, = dvi
367 # A total height (including the descent) needs to be returned.
368 return page.width, page.height + page.descent, page.descent
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/dviread.py:296, in Dvi.__iter__(self)
280 def __iter__(self):
281 """
282 Iterate through the pages of the file.
283
(...)
294 integers.
295 """
--> 296 while self._read():
297 yield self._output()
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/dviread.py:375, in Dvi._read(self)
373 while True:
374 byte = self.file.read(1)[0]
--> 375 self._dtable[byte](self, byte)
376 name = self._dtable[byte].__name__
377 if name == "_push":
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/dviread.py:227, in _dispatch.<locals>.decorate.<locals>.wrapper(self, byte)
225 if state is not None and self.state != state:
226 raise ValueError("state precondition failed")
--> 227 return method(self, *[f(self, byte-min) for f in get_args])
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/dviread.py:526, in Dvi._fnt_def(self, k, c, s, d, a, l)
524 @_dispatch(min=243, max=246, args=('olen1', 'u4', 'u4', 'u4', 'u1', 'u1'))
525 def _fnt_def(self, k, c, s, d, a, l):
--> 526 self._fnt_def_real(k, c, s, d, a, l)
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/dviread.py:531, in Dvi._fnt_def_real(self, k, c, s, d, a, l)
529 n = self.file.read(a + l)
530 fontname = n[-l:].decode('ascii')
--> 531 tfm = _tfmfile(fontname)
532 if c != 0 and tfm.checksum != 0 and c != tfm.checksum:
533 raise ValueError('tfm checksum mismatch: %s' % n)
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/dviread.py:1116, in _fontfile(cls, suffix, texname)
1114 @lru_cache
1115 def _fontfile(cls, suffix, texname):
-> 1116 return cls(find_tex_file(texname + suffix))
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/dviread.py:1082, in find_tex_file(filename)
1079 filename = filename.decode('utf-8', errors='replace')
1081 try:
-> 1082 lk = _LuatexKpsewhich()
1083 except FileNotFoundError:
1084 lk = None # Fallback to directly calling kpsewhich, as below.
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/dviread.py:1037, in _LuatexKpsewhich.__new__(cls)
1034 @lru_cache # A singleton.
1035 def __new__(cls):
1036 self = object.__new__(cls)
-> 1037 self._proc = self._new_proc()
1038 return self
File ~/anaconda3/envs/ml/lib/python3.11/site-packages/matplotlib/dviread.py:1041, in _LuatexKpsewhich._new_proc(self)
1040 def _new_proc(self):
-> 1041 return subprocess.Popen(
1042 ["luatex", "--luaonly",
1043 str(cbook._get_data_path("kpsewhich.lua"))],
1044 stdin=subprocess.PIPE, stdout=subprocess.PIPE)
File ~/anaconda3/envs/ml/lib/python3.11/subprocess.py:1026, in Popen.__init__(self, args, bufsize, executable, stdin, stdout, stderr, preexec_fn, close_fds, shell, cwd, env, universal_newlines, startupinfo, creationflags, restore_signals, start_new_session, pass_fds, user, group, extra_groups, encoding, errors, text, umask, pipesize, process_group)
1022 if self.text_mode:
1023 self.stderr = io.TextIOWrapper(self.stderr,
1024 encoding=encoding, errors=errors)
-> 1026 self._execute_child(args, executable, preexec_fn, close_fds,
1027 pass_fds, cwd, env,
1028 startupinfo, creationflags, shell,
1029 p2cread, p2cwrite,
1030 c2pread, c2pwrite,
1031 errread, errwrite,
1032 restore_signals,
1033 gid, gids, uid, umask,
1034 start_new_session, process_group)
1035 except:
1036 # Cleanup if the child failed starting.
1037 for f in filter(None, (self.stdin, self.stdout, self.stderr)):
File ~/anaconda3/envs/ml/lib/python3.11/subprocess.py:1955, in Popen._execute_child(self, args, executable, preexec_fn, close_fds, pass_fds, cwd, env, startupinfo, creationflags, shell, p2cread, p2cwrite, c2pread, c2pwrite, errread, errwrite, restore_signals, gid, gids, uid, umask, start_new_session, process_group)
1953 err_msg = os.strerror(errno_num)
1954 if err_filename is not None:
-> 1955 raise child_exception_type(errno_num, err_msg, err_filename)
1956 else:
1957 raise child_exception_type(errno_num, err_msg)
PermissionError: [Errno 13] Permission denied: 'luatex'
<Figure size 600x600 with 1 Axes>
“Pictures have actually been transmitted from Earth into outer space in this way.
Two large prime numbers were used so that a much more detailed picture could be sent.
It is reasonable to expect that a civilized recipient of such a message would be able to work out how to reconstruct the picture, since factorization of a number into prime factors is a property independent of language or notation.”
[1.2]#
Suppose the binary repetition code of length \(5\) is used for a binary symmetric channel which has symbol error probability \(p\).
Show that the word error probability of the code is
\( 10p^3-15p^4+6p^5 \)
See the page on the binary repetition code of length \(5\).
[1.3]#
Show that a code \(C\) having minimum distance \(d(C)=4\) can be used simultaneously to correct single errors and detect double errors.
[\(C\) could also be used either as a single-error-correcting code or as a triple-error-detecting code, but not both simultaneously. Why not?]
\( \begin{aligned} d(C)\ge4&=(s=3)+1 \\ d(C)\ge4&=2(t=1.5)+1 \end{aligned} \)
Suppose the vector \(\mathbf{y}\) is received.
If \(d(\mathbf{x,y})\le1\) for some codeword \(\mathbf{x}\in C\), then \(\mathbf{y}\) is closer to \(\mathbf{x}\) than to any other codeword and so it will be decoded to it (and thus corrected).
If \(d(\mathbf{x,y})\ge2\) for all codewords \(\mathbf{x}\in C\), then \(\mathbf{y}\) is equally distant from them all and so cannot be decoded to a closest codeword; and it is not a codeword; so, it can be detected.
Why is this d(x,y)>=2, and not just d(x,y)=2?
If \(d(\mathbf{x,y})=3\) for some codeword \(\mathbf{x}\in C\), then \(\mathbf{y}\) is not a codeword by the minimum distance \(d(C)=4\) of the code.
But it could be the case that \(d(\mathbf{x',y})\le1\) for some other codeword \(\mathbf{x'\ne x}\in C\).
In an error-correcting context, \(\mathbf{y}\) would be decoded to \(\mathbf{x'}\).
[1.4]#
The code used by Mariner 9 will correct any received \(32\)-tuple provided not more than how many errors have occurred?
See the page on the \((32,64,16)\) Reed-Muller code.
[1.5]#
(i) Show that a \(3\)-ary \((3,M,2)\)-code must have \(M\le9\).
Suppose \(C\) is a \((3,M,2)\)-code.
The \(M\) ordered pairs obtained by deleting the third coordinate of each codeword must be distinct; for if any two were identical, then the corresponding codewords would differ only in the third position contradicting \(d(C)=2\).
Therefore, \(M\le q^2\).
(ii) Show that a \(3\)-ary \((3,9,2)\)-code exists.
(iii) Generalize the results of (i) and (ii) to \(q\)-ary \((3,M,2)\)-codes, for any integer \(q\ge2\).
\( \{(a,b,(a+b)\mod q)\mid(a,b)\in(F_q)^2\} \)
is a \(q\)-ary \((3,q^2,2)\)-code.
q=2,(3,4,2)-code#
\( \begin{aligned} (3,4,2)&\text{-code}\subseteq(F_2)^3 \end{aligned} \)
q=2
n=3
f=fqn(q,n)
M=fqn(q,2)
C=[list(m+str(sum([int(i) for i in m])%q) for m in sorted(list(M)))]
for k in range(q-1):
C.append(list(''.join([str((int(i)+1)%q) for i in m]) for m in C[k]))
print(f"{q**n:,}")
print(f)
print(M)
pd.DataFrame(data=C)
8
{'010', '101', '111', '001', '100', '110', '000', '011'}
{'00', '01', '11', '10'}
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 000 | 011 | 101 | 110 |
| 1 | 111 | 100 | 010 | 001 |
q=3,(3,9,2)-code#
\( \begin{aligned} (3,9,2)&\text{-code}\subseteq(F_3)^3 \end{aligned} \)
q=3
n=3
f=fqn(q,n)
M=fqn(q,2)
C=[list(m+str(sum([int(i) for i in m])%q) for m in sorted(list(M)))]
for k in range(q-1):
C.append(list(''.join([str((int(i)+1)%q) for i in m]) for m in C[k]))
print(f"{q**n:,}")
print(f)
print(M)
pd.DataFrame(data=C)
27
{'221', '010', '110', '202', '102', '222', '012', '220', '100', '120', '022', '000', '200', '021', '101', '211', '112', '122', '002', '212', '210', '121', '111', '201', '001', '020', '011'}
{'11', '10', '00', '02', '12', '22', '20', '01', '21'}
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 000 | 011 | 022 | 101 | 112 | 120 | 202 | 210 | 221 |
| 1 | 111 | 122 | 100 | 212 | 220 | 201 | 010 | 021 | 002 |
| 2 | 222 | 200 | 211 | 020 | 001 | 012 | 121 | 102 | 110 |
q=4,(3,16,2)-code#
\( \begin{aligned} (3,16,2)&\text{-code}\subseteq(F_4)^3 \end{aligned} \)
q=4
n=3
f=fqn(q,n)
M=fqn(q,2)
C=[list(m+str(sum([int(i) for i in m])%q) for m in sorted(list(M)))]
for k in range(q-1):
C.append(list(''.join([str((int(i)+1)%q) for i in m]) for m in C[k]))
print(f"{q**n:,}")
print(f)
print(M)
pd.DataFrame(data=C)
64
{'213', '221', '010', '033', '311', '231', '230', '103', '330', '132', '131', '223', '110', '123', '102', '202', '133', '203', '333', '310', '222', '321', '012', '220', '100', '120', '332', '022', '301', '000', '200', '312', '021', '313', '323', '101', '211', '322', '232', '112', '303', '122', '302', '002', '013', '003', '031', '212', '331', '233', '030', '032', '210', '130', '121', '111', '113', '201', '001', '300', '023', '320', '020', '011'}
{'31', '11', '10', '33', '00', '32', '02', '12', '22', '03', '20', '13', '01', '23', '21', '30'}
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 000 | 011 | 022 | 033 | 101 | 112 | 123 | 130 | 202 | 213 | 220 | 231 | 303 | 310 | 321 | 332 |
| 1 | 111 | 122 | 133 | 100 | 212 | 223 | 230 | 201 | 313 | 320 | 331 | 302 | 010 | 021 | 032 | 003 |
| 2 | 222 | 233 | 200 | 211 | 323 | 330 | 301 | 312 | 020 | 031 | 002 | 013 | 121 | 132 | 103 | 110 |
| 3 | 333 | 300 | 311 | 322 | 030 | 001 | 012 | 023 | 131 | 102 | 113 | 120 | 232 | 203 | 210 | 221 |
q=5,(3,32,2)-code#
\( \begin{aligned} (3,32,2)&\text{-code}\subseteq(F_5)^3 \end{aligned} \)
q=5
n=3
f=fqn(q,n)
M=fqn(q,2)
C=[list(m+str(sum([int(i) for i in m])%q) for m in sorted(list(M)))]
for k in range(q-1):
C.append(list(''.join([str((int(i)+1)%q) for i in m]) for m in C[k]))
print(f"{q**n:,}")
print(f)
print(M)
pd.DataFrame(data=C)
125
{'033', '311', '231', '131', '141', '024', '123', '202', '203', '314', '410', '220', '313', '232', '122', '031', '233', '424', '422', '121', '434', '300', '143', '040', '241', '011', '213', '221', '440', '010', '404', '034', '401', '102', '004', '012', '014', '332', '421', '000', '432', '433', '211', '403', '043', '234', '042', '002', '342', '003', '030', '032', '130', '111', '324', '442', '320', '321', '224', '242', '304', '132', '223', '110', '134', '114', '310', '222', '340', '120', '022', '140', '301', '200', '312', '441', '144', '104', '142', '444', '400', '334', '302', '212', '244', '423', '341', '204', '210', '113', '343', '023', '331', '411', '420', '413', '230', '103', '330', '044', '133', '333', '443', '100', '124', '243', '412', '402', '021', '414', '041', '323', '101', '322', '112', '240', '303', '013', '344', '214', '431', '201', '430', '001', '020'}
{'22', '34', '13', '01', '31', '11', '00', '12', '30', '10', '32', '44', '43', '42', '33', '14', '02', '23', '03', '20', '04', '40', '41', '24', '21'}
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ... | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 000 | 011 | 022 | 033 | 044 | 101 | 112 | 123 | 134 | 140 | ... | 303 | 314 | 320 | 331 | 342 | 404 | 410 | 421 | 432 | 443 |
| 1 | 111 | 122 | 133 | 144 | 100 | 212 | 223 | 234 | 240 | 201 | ... | 414 | 420 | 431 | 442 | 403 | 010 | 021 | 032 | 043 | 004 |
| 2 | 222 | 233 | 244 | 200 | 211 | 323 | 334 | 340 | 301 | 312 | ... | 020 | 031 | 042 | 003 | 014 | 121 | 132 | 143 | 104 | 110 |
| 3 | 333 | 344 | 300 | 311 | 322 | 434 | 440 | 401 | 412 | 423 | ... | 131 | 142 | 103 | 114 | 120 | 232 | 243 | 204 | 210 | 221 |
| 4 | 444 | 400 | 411 | 422 | 433 | 040 | 001 | 012 | 023 | 034 | ... | 242 | 203 | 214 | 220 | 231 | 343 | 304 | 310 | 321 | 332 |
5 rows × 25 columns