\section{LDPC}

\subsection{Overview}

In APRS, a single flipped bit results in a ruined packet. In CATS, Forward Error Correction (FEC) is used to make the protocol tolerant of bit flips. LDPC has been chosen, as it is a mature algorithm which operates close to the Shannon Limit.

\subsection{Algorithm}

Like APRS, CATS packets are variable-length. This is advantageous as packets that contain small amounts of data don't need to be padded; this increases efficiency. However, LDPC encoding requires data to be of a constant width. The solution is to break our data into chunks, so that we can LDPC-encode each chunk individually.

The structure of the data chunks is not encoded in the packet. Instead, the data is broken into chunks deterministically. The same algorithm can be used by the receiver to break the chunks apart, decode them, and combine the resulting data together. The valid LDPC codes are TC128, TC256, TC512, TM2048, and TM8192, all with $r=1/2$. These codes are specified in detail in CCSDS document 231.1-0-1. The algorithm works as follows:

\begin{enumerate}
\item Pick the largest code with an input size $M \le N$
\item Take the first M bytes of data and pass them through the LDPC encoder
\item Set $N \leftarrow M - N$
\item Go to step 1, unless $N \le 32$ bits
\item Pad the remaining data with 0xAA to make it 8 bytes long
\item Run the padded data through TC128 encoder
\end{enumerate}

Note that on the final step, the 0xAA padding doesn't end up in the final packet. Only the original data and the parity data is included. \\

For example, imagine our data after adding the parity CRC is 2349 bytes long. The algorithm would work as follows:
\begin{enumerate}
\item Encode the first 512 bytes with TM8192 (1837 bytes remaining)
\item Encode the next 512 bytes with TM8192 (1325 bytes remaining)
\item Encode the next 512 bytes with TM8192 (813 bytes remaining)
\item Encode the next 512 bytes with TM8192 (301 bytes remaining)
\item Encode the next 128 bytes with TM2048 (173 bytes remaining)
\item Encode the next 128 bytes with TM2048 (45 bytes remaining)
\item Encode the next 32 bytes with TC512 (13 bytes remaining)
\item Encode the next 8 bytes with TC128 (5 bytes remaining)
\item Pad the remaining 5 bytes out to 8 bytes with 0xAA 0xAA 0xAA, then encode with TC128
\end{enumerate}

Note that the final packet length will be:
\begin{align*}
  L &= 2 + N + (512 * 4) + (128 * 2) + 32 + (8 * 2)\\
  &= 4703
\end{align*}

\subsection{Structure}

\begin{tabularx}{\textwidth}{|l|l|X|}
  \hline
  \textbf{Byte offset} & \textbf{Length} & \textbf{Data} \\
  \hline
  0 & $D_1$ & First data chunk \\
  \hline
  $D_1$ & $D_2$ & Second data chunk \\
  \hline
  $D_1 + D_2$ & $D_3$ & Third data chunk \\
  \hline
  ... & ... & ... \\
  \hline
  $\sum_{i=1}^{n-1} D_i$ & $D_n$ & $n$th data chunk \\
  \hline
  $\sum_{i=1}^{n} D_i$ & $P_1$ & LDPC parity for first chunk \\
  \hline
  $\sum_{i=1}^{n} D_i + P_1$ & $P_2$ & LDPC parity for second chunk \\
  \hline
  $\sum_{i=1}^{n} D_i + P_1 + P_2$ & $P_3$ & LDPC parity for third chunk \\
  \hline
  ... & ... & ... \\
  \hline
  $\sum_{i=1}^{n} D_i + \sum_{i=1}^{n-1} P_i$ & $P_n$ & LDPC parity for $n$th chunk \\
  \hline
  $\sum_{i=1}^{n} D_i + \sum_{i=1}^{n} P_i$ & 2 & Number of bytes after adding CRC parity (pre-LDPC encoding) \\
  \hline
\end{tabularx}