<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">%======================================================================
\section{Encoding a sample from a Conductivity-Temperature-Depth (CTD) sensor}
\label{sec_ctd_encode}

In section \ref{sec:varint}, we explored a variable integer encoder for encoding single integer (int32) fields. In this section, your goal will be to write an entropy encoder (specifically, an arithmetic encoder) for encoding temperature data from a Conductivity-Temperature-Depth (CTD) sensor (pictured in Fig. \ref{fig:sbe49}), which measures salinity (from conductivity), temperature, and depth (from pressure). CTD data are useful for vehicles performing collaborative environmental missions. They can also used to calculate the speed of sound using various empirical formulas \cite{npl_soundspeed}, so they are also invaluable for acoustic modeling in sonar-based applications. 

\begin{center}
	\includegraphics[height=6cm]{sbe49.jpg}
	\captionof{figure}{A typical vehicle CTD: the Sea-Bird SBE49 \cite{sbe49}}
	\label{fig:sbe49}
\end{center}

A traditional ship-based use of a CTD involves casting the instrument to a certain depth at a fixed location in the ocean (a ``station''). When the cast is complete, the ship can move to another station, and another CTD cast is made. In this way, one can gather (and interpolate) a three-dimensional picture of the salinity and temperature of the ocean. Since typically AUVs do not move directly vertically, a CTD profile is often made by ``yoyoing'' the vehicle; that is, the vehicle performs a series of periodic oscillations in depth while still covering ground. 


\begin{center}
	\includegraphics[width=\textwidth]{yoyo.pdf}
	\captionof{figure}{The path of a vehicle performing a sinusoidal yoyo for the purpose of collecting CTD data.}
	\label{fig:yoyo}
\end{center}

In this section, we will be assuming the vehicle is continuously sampling the ocean between 0 and 100 meters as illustrated in Fig. \ref{fig:yoyo}. \textit{A priori} (perhaps from an earlier data set or simulation), we expect the temperature profile (in depth) to be that given in Fig. \ref{fig:temp_profile}, which is defined by
\begin{equation} \label{eq:temp}
t(d)=\left\{
\begin{array}{c l}      
    20 &amp; 0 &lt;= d &lt; 10 \\
    10 + \frac{30-d}{2} &amp; 10 &lt;= d &lt; 30 \\
    10 &amp; d &gt;= 30 \\
\end{array}\right.
\end{equation}
where $t$ is the current temperature in $^\circ C$, and $d$ is depth in $m$. Given this information, it is possible for us to determine a probability mass function of the measured temperature. This will provide us with the ability to predict the samples we will obtain and thus improve the performance of the encoder used to prepare them for transmission.

\begin{center}
	\includegraphics[width=\textwidth]{temp_profile.pdf}
	\captionof{figure}{Assumed temperature profile (based off a typical Mediterranean summer profile)}
	\label{fig:temp_profile}
\end{center}

\subsection{Your Task}

Your goal in this section is to finish an arithmetic coder that will encode nearly optimally\cite{howard1992practical} the CTD samples coming from this hypothetical AUV sampling the profile given in Fig. \ref{fig:temp_profile}. Specifically, we will make some simplifying assumptions to make your task manageable in the time allotted:

\begin{itemize}
\item We will use arithmetic encoding only for the temperature; we will send depth and salinity values using the default DCCL codecs (bounded real numbers).
\item We will send the temperature values (in $^\circ C$) rounded to the nearest integer. This means we will be transmitting from a set of eleven symbols: \{10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20\}.
\item We will send exactly five samples per transmission (which means encoding five samples at a time). This means you will not run into trouble using the double precision floating point type (\texttt{double}) to hold the entire encoded answer range. For this assignment you do not need to worry about a variable number of samples per transmission (though in general you would want to consider this using an end-of-file or EOF symbol). This all means you can use the basic approach diagrammed in the table at the top of page 4 in Howard and Vitter's paper, and not worry about using integer arithmetic or interval expansion.
\end{itemize}

Also, to avoid spending all the time you have working out the necessary software ``plumbing'', we've provided you with a partially implemented codec:
\begin{verbatim}
moos-ivp-extend-acomms/src/codecs/arithmetic.cpp
moos-ivp-extend-acomms/src/codecs/arithmetic.h
\end{verbatim}

The DCCL message \texttt{CTDMessage} you will be sending is defined in 
\begin{verbatim}
moos-ivp-extend-acomms/src/protobuf/ctd.proto
\end{verbatim}

A very similar message \texttt{CTDMessage} using the DCCL default codecs is defined in
\begin{verbatim}
moos-ivp-extend-acomms/src/protobuf/ctd_default.proto
\end{verbatim}
and will form the basis of comparison with the arithmetic coder.

Finally, we have provided a unit test \texttt{ctd\_tester} in
\begin{verbatim}
moos-ivp-extend-acomms/src/ctd_tester/main.cpp
\end{verbatim}
that runs a number of encode/decode tests on your arithmetic coder. It checks two deterministic cases: the ``best case'' (temperature = \{10, 10, 10, 10, 10\}), and a ``worst case'' (temperature = \{19, 19, 18, 17, 17\}). Then it checks ten random sets of temperatures sampled by uniformly placing the vehicle in [0, 100] meters in depth, then reading the value off Fig. \ref{fig:temp_profile}. Obviously a real vehicle couldn't do this, but it serves to check our coder's functionality and performance.
To run this unit test:
\begin{verbatim}
cd moos-ivp-extend-acomms
./build.sh
ctd_tester
\end{verbatim}
Until you finish the ArithmeticCoder class, \texttt{ctd\_tester} will assert-fail\footnote{Assertions are debugging / testing tool that cause the program to exit with an error message if the contents of the \texttt{assert} macro is false.} with a message like:
\begin{verbatim}
ctd_tester: /home/toby/moos-ivp-extend-acomms/src/ctd_tester/main.cpp:97:
void run_test(const std::vector&lt;double&gt;&amp;): Assertion 
`msg_in1.SerializeAsString() == msg_out1.SerializeAsString()' failed.
\end{verbatim}

\subsection{Approach}

This section outlines a step-by-step approach to this problem:

\begin{enumerate}
\item Ensure you understand the basics of arithmetic encoding by reading the first two sections of \textit{Practical Implementations of Arithmetic Coding} by P. Howard and J. Vitter \cite{howard1992practical}. This was the pre-lab assignment, but it may be helpful to have the paper handy. You may also find Chapter 4 from \textit{Introduction to Data Compression} \cite{sayood_introduction_2005} useful for more details. Both of these papers are on the class Stellar site.
\item Given that the vehicle is assumed be uniformly distributed between 0 and 100 meters, as given by
\begin{equation}
p_D(d)=\left\{
\begin{array}{c l}      
    0.01 &amp; 0 &lt;= d &lt; 100\\
    0 &amp; \hbox{otherwise}
\end{array}\right.
\end{equation}
where $D$ is the random variable indicating the vehicle's depth (in meters) below the sea surface. Combining this with the (assumed) deterministic model for temperature over depth given in Fig. \ref{fig:temp_profile} and Eq. \ref{eq:temp} you should fill in Table \ref{fig:pmf} for the probability mass function for the temperature symbols (random variable $T$). Make sure your probabilities sum to one:
\begin{equation}
\sum_{t = 10}^{20} p_T(t) = 1
\end{equation}

\ifx\answer\undefined 
\begin{table}
\caption{Probability mass function of sampled temperature.}
\label{fig:pmf}
\begin{center}
\begin{tabular}{ | c | c | }
  \hline
   Symbol $t$ (temperature) &amp; $p_T(t)$  \\ \hline
  \hline
   10 &amp;  \\ \hline
   11 &amp;  \\ \hline
   12 &amp;  \\ \hline
   13 &amp;  \\ \hline
   14 &amp;  \\ \hline
   15 &amp;  \\ \hline
   16 &amp;  \\ \hline
   17 &amp;  \\ \hline
   18 &amp;  \\ \hline
   19 &amp;  \\ \hline
   20 &amp;  \\ \hline
\end{tabular}
\end{center}
\end{table}
\else
\begin{table}
\caption{Probability mass function of sampled temperature.}
\label{fig:pmf}
\begin{center}
\begin{tabular}{ | c | c | }
  \hline
   Symbol $t$ (temperature) &amp; $p_T(t)$  \\ \hline
  \hline
   10 &amp; {\color{red} 0.71 }  \\ \hline
   11 &amp; {\color{red} 0.02 }  \\ \hline
   12 &amp; {\color{red} 0.02 }  \\ \hline
   13 &amp; {\color{red} 0.02 } \\ \hline
   14 &amp; {\color{red} 0.02 } \\ \hline
   15 &amp; {\color{red} 0.02 } \\ \hline
   16 &amp; {\color{red} 0.02 } \\ \hline
   17 &amp; {\color{red} 0.02 } \\ \hline
   18 &amp; {\color{red} 0.02 } \\ \hline
   19 &amp; {\color{red} 0.02 } \\ \hline
   20 &amp; {\color{red} 0.11 } \\ \hline
\end{tabular}
\end{center}
\end{table}
\fi

You may wish to check your values with me before implementing any code. 
\item Implement the remaining virtual methods in \texttt{arithmetic.cpp} to finish defining our custom codec \texttt{ArithmeticCodec}:
\begin{verbatim}
Bitset encode_repeated(const std::vector&lt;goby::int32&gt;&amp; wire_values);
std::vector&lt;goby::int32&gt; decode_repeated(const Bitset&amp; bits);
unsigned max_size_repeated();
unsigned min_size_repeated();
\end{verbatim}
These functions should be relatively well explained in \texttt{arithmetic.h}. If you are interested, the Doxygen documentation for DCCLRepeatedTypedFieldCodec, giving all the member functions and some brief explanation, is available at \url{http://gobysoft.com/doc/2.0/classgoby_1_1acomms_1_1DCCLRepeatedTypedFieldCodec.html}. 
A few notes to avoid unnecessary difficulty or confusion:
\begin{itemize}
\item The type \texttt{goby::int32} is used to make all the behind-the-scenes templating work correctly (it's a \texttt{typedef} for \texttt{google::protobuf::int32} which corresponds to the \texttt{int32} type in the protobuf file). You can use it like a normal \texttt{int}, which it probably is on your system anyway.
\item All sizes are in bits (e.g. return value in \verb|unsigned max_size_repeated();|). There are eight bits to a byte.
\item \verb|unsigned max_size_repeated();| must return an upper bound $U$ (in bits) for the worst case number of bits the encoder will use. In this implementation of the arithmetic encoder,
\begin{equation} \label{eq:worst}
U = \left\lceil N \log_2(\frac{1}{p_{min}}) \right\rceil + 1
\end{equation}
where $N$ is the number of symbols (five in this case), $p_{min}$ is the minimum probability of any of the symbols. You may notice that this is almost the number of bits given by the entropy (in an information content sense) of this probability distribution. The lower bound case, \verb|unsigned min_size_repeated();|, is very similar, except of course it is governed by the most likely outcome.
\item The type \texttt{goby::acomms::Bitset}\footnote{\url{http://gobysoft.org/doc/2.0/classgoby_1_1acomms_1_1Bitset.html}} is a basically a \texttt{std::deque&lt;bool&gt;} with some additional features. To avoid some of the nuisance of learning \verb|goby::acomms::Bitset|, we've provided two helper functions: \verb|range_to_bits| for encoding the decimal range you will provide and \verb|bits_to_range| for decoding.
\item \verb|range_to_bits|, which is provided for you, converts a double precision \verb|std::pair| decimal range that is a subset of [0, 1) such as [0.25,0.265625) into the shortest binary fraction that uniquely identifies the range, e.g. 000010. The \verb|Bitset| output (e.g. $000010$) has the least significant bit as the largest fraction ($2^{-1}$) and the most significant bit as the smallest fraction ($2^{-6}$). In regular mathematical notation, this would be written as $0.01000$, and means in decimal:
\begin{verbatim}
000010
||||||-&gt;0*2^-1 +
|||||-&gt;1*2^-2 +
||||-&gt;0*2^-3 +
|||-&gt;0*2^-4 +
||-&gt;0*2^-5 +
|-&gt;0*2^-6
---------------
0.25
\end{verbatim}

\item \verb|bits_to_range| takes a \verb|Bitset| generated by \verb|range_to_bits| and returns the range uniquely identified by that \verb|Bitset|. Since we are forced to work in whole bits, the returned range from \verb|bits_to_range| is generally a proper subset (a smaller range) of the original range passed to \verb|range_to_bits|. For example, if we write the code 
\begin{verbatim}
Bitset bits = range_to_bits(std::make_pair(lower, upper));
std::pair&lt;double, double&gt; result = bits_to_range(bits);
            
std::cout &lt;&lt; i &lt;&lt; ": " &lt;&lt; std::setprecision(15)
          &lt;&lt; "in: [" &lt;&lt; lower
          &lt;&lt; ", " &lt;&lt; upper
          &lt;&lt; "), out: [" 
          &lt;&lt; result.first &lt;&lt; "," &lt;&lt; result.second &lt;&lt; ")"
          &lt;&lt; ", bits: " &lt;&lt; bits &lt;&lt; std::endl;
\end{verbatim}
and run it ten times with random inputs to \verb|double lower| and \verb|double upper|, the result looks like:
\begin{small}
\begin{verbatim}
1: in: [0.224450518947304, 0.272736707829282), out: [0.25,0.265625), bits: 000010
2: in: [0.343518942754492, 0.498916563810276), out: [0.375,0.4375), bits: 0110
3: in: [0.181075460361818, 0.735460476826625), out: [0.25,0.5), bits: 10
4: in: [0.169450353444298, 0.263964024960978), out: [0.1875,0.25), bits: 1100
5: in: [0.478094624578066, 0.73305528551948), out: [0.5,0.625), bits: 001
6: in: [0.796269196922085, 0.977315562766658), out: [0.875,0.9375), bits: 0111
7: in: [0.139742564009383, 0.416557414651177), out: [0.25,0.375), bits: 010
8: in: [0.219583303769856, 0.34400233828649), out: [0.25,0.3125), bits: 0010
9: in: [0.415195364698393, 0.418356456988657), out: [0.416015625,0.41796875),
	 bits: 101010110
10: in: [0.350675355340669, 0.812326993705857), out: [0.5,0.75), bits: 01
\end{verbatim}
\end{small}
Not surprisingly, tighter ranges take more bits to represent. More probable results lead a larger range to encode. Thus, more probable events have smaller encoded sizes, leading to the desired result.
\item When your method \verb|std::vector&lt;goby::int32&gt; decode_repeated(const Bitset&amp; bits);| is called, \verb|bits| \textit{only} contains the $N_{min}$ number of least significant bits required to decode, where $N_{min}$ is the value returned by \verb|unsigned min_size_repeated();|. To get more bits from your parent class (which you will need in all but the best case situation), call the function \verb|get_more_bits(unsigned n)|, where $n$ is the number of bits requested. The requested bits are placed at the most significant end of \verb|bits|. \textbf{You must request exactly the number of bits you provided at encode\_repeated} or you will break the encoding and probably throw a \verb|std::bad_alloc| exception as DCCL tries to provide more bits than are available. The shell version of \verb|ArithmeticCodec| provided to you gives an example of how to request the remaining bits and where they are placed. In your final design, you will probably be requesting one bit at a time until you have reached the necessary precision to fully determine the five symbols you encoded.
\end{itemize}
\item Test your codec using the \verb|ctd_tester| unit test previously described. The result should look something like:
\begin{footnotesize}
\begin{verbatim}
= Begin CTDMessage =
Actual maximum size of message: ?? bytes / ??? bits [dccl.id head: 8, user head: 0, ...
Allowed maximum size of message: 32 bytes / 256 bits
== Begin Header ==
== End Header ==
== Begin Body ==
CTDMessage
 repeated int32 depth = 1;
 :: size = 50 bit(s)
 repeated int32 temperature = 2;
 :: min size = ?? bit(s)
 :: max size = ?? bit(s)
 repeated double salinity = 3;
 :: size = 55 bit(s)
:: min size = ??? bit(s)
:: max size = ??? bit(s)
== End Body ==
= End CTDMessage =
****************** BEGIN TEST 0 ******************* 
In: depth: [12, 13, 14, 13, 13] temperature: [19, 19, 18, 17, 17] salinity: [30.09, 30.1,...
Try encode ...
Encoded (hex): 660d38f080030e1c94154bfffc0740011210
Size (bytes): ??
Default codec size (bytes): 17
Try decode...
Out: depth: [12, 13, 14, 13, 13] temperature: [19, 19, 18, 17, 17] salinity: [30.09, 30.1, ...
***************** PASSED TEST 0 ****************** 

****************** BEGIN TEST 1 ******************* 
In: depth: [12, 13, 14, 13, 13] temperature: [10, 10, 10, 10, 10] salinity: [30.09, 30.1, ...
Try encode ...
Encoded (hex): 660d38f080030ec03fff0150800404
Size (bytes): ??
Default codec size (bytes): 17
Try decode...
Out: depth: [12, 13, 14, 13, 13] temperature: [10, 10, 10, 10, 10] salinity: [30.09, 30.1, ...
***************** PASSED TEST 1 ****************** 

(... and similar through TEST 11 ...)

all tests passed
\end{verbatim}
\end{footnotesize}
(we've added \verb|??| to some places which will be actual numbers in your output).
\end{enumerate}


\subsection{Questions}

Some quick questions for you to consider and hand in with your completed ArithmeticCodec by Thursday April 5.

\ifx\answer\undefined
\else
{\color{red}
My solution example arithmetic coder is available for checkout in the same bazaar repository you used earlier:
\begin{verbatim}
bzr co lp:~tes/junk/moos-ivp-extend-acomms moos-ivp-extend-acomms-answers
\end{verbatim}
See \verb|moos-ivp-extend-acomms-answers/src/codecs/arithmetic.cpp|.
}
\fi

\begin{enumerate}
\item If you run \verb|analyze_dccl| on \verb|ctd_default.proto|, you find
\begin{verbatim}
 repeated int32 temperature = 2;
 :: size = 20 bit(s)
\end{verbatim}
\begin{enumerate}
\item How does the size of the encoded message from your arithmetic coder compare to that of the default DCCL encoder? (hint: if the return value from \verb|encode_repeated| is called \verb|data_bits|, use
\begin{verbatim}
std::cout &lt;&lt; data_bits.size() &lt;&lt; std::endl;
\end{verbatim}
to show how many bits your arithmetic encoding takes). 
\item Does the arithmetic encoder always outperform the default encoder? If not, in which cases does it underperform and in which cases does it overperform?
\item Calculate the expected size (in bits) of the encoded message using your arithmetic encoder, assuming the distribution you calculated in Table \ref{fig:pmf}. Using this value, what percentage improvement does the arithmetic encoder provide on average from the DCCL default encoder?
\end{enumerate}

\ifx\answer\undefined
\else
{\color{red}
In some cases (e.g. [11, 12, 13, 14, 15]) the DCCL default encoder outperforms the arithmetic coder. These are the highly improbable cases (assuming our model is correct, which is an assumption one must make carefully in the real world). In the more probable cases (e.g. [20, 20, 20, 20, 20]), the arithmetic coder outperforms the default one. A few numbers for comparison:

\begin{center}
	\begin{tabular}{|l|l|} \hline
		Scenario &amp; Encoded size (bits) \\ \hline \hline
		DCCL Default (any symbols) &amp; 20 \\ \hline
		Arithmetic (best case) &amp; 3 \\ \hline
		Arithmetic (expected case) &amp; 8.72 \\ \hline
		Arithmetic (worst case) &amp; 30 \\\hline
	\end{tabular}
	\label{tab:answer_sizes}
\end{center}

The best case can be computed using
\begin{eqnarray*}
l_{min} &amp;=&amp; -\log_2(p_{max}) \\
        &amp;=&amp; -\log_2(0.71^5) \\
        &amp;=&amp; 2.47
\end{eqnarray*}
which rounds up to 3 since we can only use whole bits.

The expected case can be computed by using 
\begin{eqnarray*}
E[L] = -\sum_i p_i \log_2(p_i)
\end{eqnarray*}
where 
\begin{itemize}
\item $p_i$ is the probability of any one set of symbols (in our case, since we have messages of 5 symbols from an 11-symbol table, $i$ ranges from $1$ to $11^5$). You can calculate all the $p_i$ using the multinomial theorem (with power 3 since we only have 3 unique probability values: 0.71, 0.11, 0.02).
\item $L = -log_2(p_i)$ is the self-information of $p_i$ and very close to the message size (in bits) created by an arithmetic coder.
\end{itemize}

The worst case is computed using Eq. \ref{eq:worst}. The perhaps not intuitive ``+1 bit'' in that equation comes from inefficiencies caused by the placement of our symbols in the range. E.g. if we have symbols A ($p_A=0.25$), B ($p_B = 0.5$), and C ($p_C = 0.25$) represented by the ranges [0, 0.25), [0.25, 0.75), [0.75, 1) respectively, encoding B requires 2 bits (0.10) even though the information content ($-\log_2(0.5))$ is 1 bit. If instead we used B = [0, 0.5), A = [0.5, 0.75), C = [0.75, 1), B would only require 1 bit (0.0). 

In short, if our model is accurate (or close to accurate), it makes sense to use the arithmetic coder for this scenario and saves us 11.28 bits on average (56\%).
}
\fi


\item How could you improve the performance of the arithmetic coder even more in this situation (hint: think about the sensor's sampling process and the AUV's realistic motion through the water)? 

\ifx\answer\undefined
\else

{\color{red}
The improvements come from the fact that the AUV cannot teleport. Thus, if we condition (or parameterize, depending on your philosophical view of whether the AUV's depth is a random variable) the probability distribution for temperature $p_T(t)$ on depth (treated as a random variable), we can produce a more realistic distribution $p_{T|D}(t|d)$ (and more efficient encoding since our model more closely fits reality). The trickiness now comes in ensuring the encoder and decoder share the same initial state. This could be done by including the depth values used to encode in the message (as is done in the CTDMessage example here). The first temperature value is then encoded conditioned on the first depth value, and so on. The decoder reads the depth values first and uses these to decode the temperatures (assuming the conditional probability $p_{T|D}(t|d)$ is shared ahead of time).

In the simplified example we worked here (Eq. \ref{eq:temp}), using this information would lead to a free (0-bit!) encoding of temperature. In the real world, we don't know \textit{a priori} the exact distribution we are about to sample (otherwise why bother sending down an AUV at all), so a reasonable $p_{T|D}(t|d)$ might be
\begin{equation}
p_{T|D}(t|d)=\left\{\begin{array}{c l}      
    \mathcal{N}(20, \sigma^2) &amp; 0 &lt;= d &lt; 10 \\
    \mathcal{N}(10 + \frac{30-d}{2}, \sigma^2) &amp; 10 &lt;= d &lt; 30 \\
    \mathcal{N}(10, \sigma^2) &amp; d &gt;= 30 \\
\end{array}\right.
\end{equation}
using a normal distribution ($\mathcal{N}(\mu, \sigma^2)$) to model our uncertainty. The variance $\sigma^2$ must be chosen to represent our uncertainty in our model of temperature. 

Further improvements could be had by updating our model as we measure it. For example, we could make $\sigma^2$ smaller as our measurements matched with our model or larger as they did not. Of course, this change has to be propagated to the receiver which adds data overhead (and the chance of getting lost).


}
\fi

\end{enumerate}




</pre></body></html>