Example: Encode and DecodeΒΆ

In this example we show how to use the low-level API of kodo-slide to implement encoding and decoding.

The following classes from kodo-slide will be used:

  • The class encoder and class decoder classes exposes a low-level API of a sliding window code. Giving you full control over the operations.
  • The struct stream is a simple adapter over a std::deque but with an API which matches the one used in kodo-slide.
  • The next helper we will use is the struct rate_controller. This object will allow us to specify in which pattern to generate repair/redundancy. See also Parameter selection.

In this example we will walk through the basic functionality and discuss how to use it.

Note

If you see an unfamiliar term used, try to visit the Definitions section and you should find a description.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
#include <algorithm>
#include <iostream>
#include <memory>
#include <vector>

// The first thing we need to do is to include the
// relevant header files.

// Encoder and decoders
#include <kodo_slide/decoder.hpp>
#include <kodo_slide/decoder_factory.hpp>
#include <kodo_slide/encoder.hpp>
#include <kodo_slide/encoder_factory.hpp>

// Helpers
#include <kodo_slide/rate_controller.hpp>
#include <kodo_slide/stream.hpp>

// In a real application we would be encoding and
// decoding symbols from some real-life source, such
// as a video feed or network card. In this example we
// will just imagine having such a source and produce
// some random data (for this purpose we implement some helpers):

using symbol_ptr = std::unique_ptr<std::vector<uint8_t>>;

symbol_ptr make_symbol(uint32_t size)
{
    symbol_ptr data = std::make_unique<std::vector<uint8_t>>();
    data->resize(size);
    return data;
}

symbol_ptr generate_symbol(uint32_t size)
{
    symbol_ptr data = make_symbol(size);

    // Just fill with some random data
    std::generate(data->begin(), data->end(), rand);
    return data;
}

int main()
{
    // Set the window size (this is the number of symbols included
    // in an encoded symbol).
    uint64_t window_symbols = 20U;

    // Set the capacity of the decoder (this is the number of
    // encoded symbols that are used in the decoding process).
    uint64_t decoder_capacity = 40U;

    // The size of a symbol in bytes
    uint64_t symbol_size = 160U;

    // Create the encoder and decoder
    kodo_slide::encoder_factory encoder_factory;
    kodo_slide::decoder_factory decoder_factory;

    encoder_factory.set_symbol_size(symbol_size);
    decoder_factory.set_symbol_size(symbol_size);

    auto encoder = encoder_factory.build();
    auto decoder = decoder_factory.build();

    // Buffers needed to store coding coefficients and symbol.
    std::vector<uint8_t> coefficients;
    std::vector<uint8_t> symbol;

    // Containers for keeping memory alive and track the
    // state of the different symbols.
    kodo_slide::stream<symbol_ptr> input_symbols;
    kodo_slide::stream<symbol_ptr> output_symbols;
    kodo_slide::stream<bool> decoded_symbols;

    // Control the amount of repair/redundancy generated
    // n: Total number of symbols
    // k: Number of source symbols out of the total
    //
    // To get a good decoding performance the rate needs to be
    // lower than or equal to the packet loss probability. In
    // this case our rate is k/n = 4/10 = 40% and our packet
    // loss probability is 50% so this should be sufficient for
    // a good decoding performance.
    //
    // The above serves as a rule of thumb - more rigorous mathematics
    // can be used to derive tighter bounds given a certain
    // decoding probability.

    uint32_t n = 10;
    uint32_t k = 4;

    kodo_slide::rate_controller rate {n, k};

    // Maximum number of interations
    uint32_t max_iterations = 1000U;
    uint32_t iterations = 0;

    // Counter for keeping track of the number of decoded symbols
    uint32_t generated = 0;
    uint32_t decoded = 0;

    while (iterations < max_iterations)
    {

        // Manage the encoder's window
        if (!rate.send_repair())
        {
            if (encoder.window_symbols() == window_symbols)
            {
                // If window is full - pop a symbol before pushing a new one
                encoder.pop_back_symbol();
                input_symbols.pop_back();
            }

            // Create a new source symbol
            auto symbol = generate_symbol(symbol_size);

            // Add the symbol's memory to the encoder
            encoder.push_front_symbol(symbol->data());

            // Store the symbol
            input_symbols.push_front(std::move(symbol));

            ++generated;
        }

        // Choose a seed for this encoding
        uint64_t seed = rand();

        // Encode a symbol
        encoder.set_window(encoder.stream_lower_bound(),
                           encoder.stream_symbols());

        // Resize buffers
        coefficients.resize(encoder.coefficient_vector_size());
        symbol.resize(encoder.symbol_size());

        // Set the seed used to generate the coding coefficients and
        // encode the symbol
        encoder.set_seed(seed);
        encoder.generate(coefficients.data());
        encoder.write_symbol(symbol.data(), coefficients.data());

        // Update loop state
        ++iterations;
        rate.advance();

        if (rand() % 2)
        {
            // Simulate 50% packet loss
            continue;
        }

        // Move the decoders's window / stream if needed
        //
        // If the encoder includes symbols in its window that the decoder
        // does not have. We need to update the state of the decoder.
        // In the following we will go through two cases:
        //
        // Case 1: The decoder can move its stream front by adding more
        //         symbols. This is possible if it has not reached the
        //         maximum capacity yet.
        //
        // Case 2: If the decoder is a maximum capacity it needs to
        //         slide its window/stream - dropping symbols that are
        //         now too "old".

        if (decoder.stream_upper_bound() < encoder.stream_upper_bound())
        {
            // If we can add more memory to the decoder lets do that
            while (decoder.stream_symbols() < decoder_capacity)
            {
                // Create a new symbol
                auto symbol = make_symbol(symbol_size);

                // Add the symbol's memory to the decoder
                decoder.push_front_symbol(symbol->data());

                // Store the symbol
                output_symbols.push_front(std::move(symbol));

                // Track the decoded state of this symbol
                decoded_symbols.push_front(false);
            }
        }

        // Check if the decoder's stream is still behind the encoder
        while (decoder.stream_upper_bound() < encoder.stream_upper_bound())
        {
            // Remove the "oldest" symbol
            decoder.pop_back_symbol();

            auto symbol = std::move(output_symbols.back());
            output_symbols.pop_back();

            decoded_symbols.pop_back();

            // Recycle the symbol
            decoder.push_front_symbol(symbol->data());
            output_symbols.push_front(std::move(symbol));
            decoded_symbols.push_front(false);
        }

        // Consume the encoded symbol
        decoder.set_window(encoder.window_lower_bound(),
                           encoder.window_symbols());

        decoder.set_seed(seed);
        decoder.generate(coefficients.data());
        decoder.read_symbol(symbol.data(), coefficients.data());

        // New symbols may now be decoded.
        for (uint64_t i = 0; i < decoder.stream_symbols(); ++i)
        {
            uint64_t index = i + decoder.stream_lower_bound();

            if (!decoder.is_symbol_decoded(index))
            {
                // This symbol has not yet been decoded
                continue;
            }

            if (decoded_symbols[index] == true)
            {
                // We've already marked this symbol decoded
                continue;
            }

            ++decoded;
            decoded_symbols[index] = true;

            std::cout << "Decoded index = " << index << "\n";
        }
    }

    std::cout << "Generated symbols = " << generated << "\n";
    std::cout << "Decoded symbols = " << decoded << "\n";

    return 0;
}