\documentclass[12pt]{article}

\usepackage{fullpage,amsmath,amsfonts}

\begin{document}

\title{Foundations of Information Systems}
\author{Winter Semester 2024--25, Exercise 10}
\date{For discussion on Wednesday, January 15, 2025}
\maketitle

\begin{enumerate}
\item In a RAID-5 array, one disk out of 5 has failed.  The others
contain the bit sequences $10001011\ldots$, $11111000\ldots$,
$00000000\ldots$, $01011010\ldots$.  Reconstruct the beginning of the
bit sequence of the failed disk.

\item Decimal codes regularly entered by humans, such as IBANs, use a
modulo-$97$ checksum.  Direct computation of such a checksum for long
sequences requires arbitrary-length integer arithmetic, which is not
directly available in hardware.  As an alternative, it is possible to
compute the modulo-$97$ checksum of the first $k$ digits, prepend the
result to the remaining digits and repeat in chunks of $k$ digits,
until the entire sequence is consumed.

Why does this work?

\emph{Hint:} If $a \equiv a' \mod 97$, then
$10^k \, a + b \equiv 10^k \, a' + b \mod 97$.  Why?

\item Check if the following IBANs are valid.  Show all of the
required steps explicitly.

\begin{enumerate}
\item DE51 7509 0300 0007 6333 00
\item DE51 7509 0300 0007 3633 00
\end{enumerate}

\item Write out the $(12,8)$ Hamming code for the binary word
$01010111$.
\item Which of the following $(7,4)$ Hamming codes are correct,
assuming that they contain at most a single-bit error?  Correct any
error you detect.
\begin{enumerate}
\item $0010111$ \item $1111111$ \item $0110101$
\end{enumerate}
\item Detect double-bit errors and correct single-bit errors in the
following words originally encoded as a $(8,4)$ Hamming code.  (We are
taking the convention from class that the overall parity bit is
first.)
\begin{enumerate}
\item $00110011$ \item $10111100$ \item $10100001$ \item $00110101$
\end{enumerate}


\item Suppose each bit can flip with a probability of $1/100$, and
that bits errors are statistically independent. What is the
probability that a $4$ bit message is received correctly when using
\begin{enumerate}
\item no error correction, 
\item a $(7,4)$ Hamming code,
\item an $(8,4)$ Hamming code with retransmission?  (You may make
sensible simplifying assumptions.)
\end{enumerate}

\end{enumerate}
\end{document}
