(Last Mod: 27 November 2010 21:37:20 )
NOTE: WORK VERY MUCH IN PROGRESS
Present concurrent codecs are block oriented (as opposed to streaming) meaning that data has to be segmented into blocks, transmitted individually, and then reassembled at the receiving end. The layers above the codec are generally responsible for the segmentation and reassembly functions and do so by breaking the data into smaller chunks and adding the information needed to perform these functions such as sequence numbers and validation information such as a digital signature. What is passed to the codec is a block of data of the appropriate length to be transformed and transmitted as a single BBC codeword.
Encoding a block of data using the BBC algorithm is conceptually accomplished as a two-step process. The first step is to take the block of data, the "message", and transform it into a padded BBC message by adding additional data bits that enhance the robustness of the decoder. The second step is to take the padded BBC message and transform it into the actual BBC codeword. This step has relatively few options, as most of the enhancements are taken care of by the padding process.
Decoding a packet containing BBC-encoded codewords essentially follows the reverse procedures of the encoding process. The received packet guides a search of the encoding tree that, in theory, recovers a list of all of the padded BBC messages whose codewords are covered by the packet. The padding information is then stripped out and the original messages passed on to the higher layers, which performs any needed validation and reassembly.
In practice both steps, both in the encoder and decoder, can be combined into single operations with the use of an appropriate state machine.
M=256 - Message Length
C=65,536 - Codeword Length
K=32 - Terminal Checksum Length
R=0 - Random Preamble Length
F=1 - Interstitial Checksum Message Fragment Length
S=0 - Interstitial Checksum Length
H=1 - Hash Block Length
B=1 - Marks per Hash Block
W=1 - Mark Width
G=0 - Mark Growth
J=0 - Jitter Window Halfwidth
P=0 - Oscillator Mismatch Allowance (ppm)
V=0 - Virtual Mark Limit
Q=1 - Quorum Requirement
A concurrent codec, particularly the decoder, can be very simple or quite elaborate, depending on which enhancements are supported. Most of the codec parameters are optional. In fact, the only two that are absolutely required are C and M, the codeword and message lengths, respectively. However, since at least a few terminal checksum bits are essential to prevent significant numbers of hallucinations from being realized, K is considered a required parameter for the most basic BBC codec, known as "Vanilla BBC".
The expansion factor, E, is an indirect way of specifying the codeword length, C. The two are related through the simple relationship C=M*E. In practice, it is often more meaningful to talk about a codec's expansion factor since this is tightly related to the system's effective processing gain. However, since C and M are required to be precise and exact integers, while the expansion factor merely has to be rational, they are the better choices for generic configuration parameters.
The basic BBC codec configuration requires only three parameters, the message length, M, codeword length, C (alternatively specified via the expansion factor, E) and the number of terminal checksum bits, K.
Data is presented to the encoder as message blocks that are M bits long. It is conceivable to use variable length blocks using a number of different techniques, most of which are used in other messaging protocols. However, to date, none of these have been explored in any depth.
The codeword generated by the encoder is C bits in length.
The expansion factor, E, is an indirect way of specifying the codeword length, C. The two are related through the simple relationship C=M*E. In practice, it is often more meaningful to talk about a codec's expansion factor since this is tightly related to the system's effective processing gain. However, since C and M are required to be precise and exact integers, while the expansion factor merely has to be rational, they are the better choices for generic configuration parameters.
The message is padded by appending K zero bits to the end of the message. The checksum bits add additional marks to the codeword at locations that are functions of the entire message, and hence serve as true checksum bits.
Unlike the other parameters, the template style is a code referring to a defined static template that is used as the starting point for constructing a BBC codeword. The present options are:
By prefixing the message with R bits, whose values are chosen at random, certain attacks are mitigated. In particular, if the decoder is comprised of multiple, independent decoders, then an attack that aims to flood a decoder with false messages will have a harder time blocking legitimate messages.
By inserting S checksum (zero) bits between each group of F message bits, the ability to successfully decode packets with densities well in excess of 50% becomes possible. Furthermore, for a narrow range of conditions, interstitial checksum bits can result in faster absolute decoding of packets despite the longer padded messages.
Multimark BBC places B marks in the codeword for every H bits of the padded message. If B<H, the codeword becomes more sparse, compared to non-Multimark BBC, but the critical density decreases accordingly. If B>H, the critical density is increased but the codeword becomes less sparse.
The principle purpose of Multimark BBC is to enable the decoder to use a Quorum of marks to determine if a block of message bits has been found. This is a means of permitting the decoder to tolerate non-zero mark error rates. For instance, if B is 3 and Q is 2, then only two of the three marks placed by the encoder must be detected in order for the block of H padded message bits to be declared present.
Whenever the encoder places a mark at a particular location within a codeword, it will also place marks in the adjacent positions such that the mark occupies a total of W locations. By making each mark span additional positions within the codeword, the likelihood that clock jitter or Doppler shift will result in the decoder failing to detect a mark can be significantly reduced. It does, however, increase the codeword density and, thus, reduces the effective processing gain.
If W is odd, then one mark is placed at the nominal location and ((W-1)/2) marks are placed before and the same number after the mark. If the W is even, then the additional mark is placed after the nominal location. Note that this means that the memory allocated to the codeword must be able to accommodate marks both before and after the normal extents of the codeword.
If Mark Width is set to zero, then the default mark width will be used. The default mark width is normally set to 1, however it may be any value, including 0. If it is zero, then the encodeer will be unable to place marks in the codeword. This has the effect of silencing the encoder.
Jitter compensation can also be performed in the decoder using a non-zero Jitter Window.
Mark Growth is a means of compensating for oscillator mismatch by making marks that appear later in a codeword wider than those that appear earlier. The width of each mark is increased to span G*Mark_Width bits-per-megabit from the start of the packet and centered on the nominal location.
While Mark Growth has no effect on the first bit of the codeword, it is largest for the last bit of the codeword and, like Mark Width, requires that the codeword be allocated sufficient memory to accommodate it.
Oscillator mismatch can also be compensated for by the decoder by using a non-zero Oscillator Mismatch window.
When the decoder looks for a mark within a packet, there exists the possibility that the receiver successfully detected the mark but placed it in the wrong location within the packet. To compensate for this, the decoder can use a Jitter Window which says that it will consider a mark found if there exists a mark in any of the locations within J of the nominal location. However, an attackers marks will also be artificially enhanced by the same amount.
Jitter compensation can also be performed by the encoder using a non-zero Mark Width.
Since BBC is a completely asynchronous communications protocol, the probability that bit alignment will be lost during the decoding phase must be taken into consideration, especially in light of the long packet lengths involved. One way to do this, at the expense of increased decoder workload, is to use bookend marks at the start and end of each packet to compensate for oscillator mismatch when decoding a packet. The parameter P is the maximum mismatch, in parts-per-million (ppm), that is to be allowed for.
Oscillator Mismatch can also be compensated for by the encoder by using a non-zero Mark Growth parameter.
The use of virtual marks is a means of tolerating non-zero mark error rates. Essentially, the decoder is allowed to ignore up to V missing marks for each prefix in the decoding tree. Unfortunately, V must be kept very small since each prefix of each legitimate message (that has no missing mark to that point) will result in and exponential number of false prefixes before they die naturally. There are, however, several possible ways to mitigate this problem that have yet to be explored.
Used in conjunction with Multimark BBC, the quorum requirement dictates the minimum number of the B marks placed in a codeword that must be detected in order for the corresponding block of H padded message bits to be considered found.
The following types of padding bits can be added to a BBC message to form the padded message:
Conceptually, each type of padding bit is added to the message in the order given above. First, the preamble field is attached by prepending a string of R random bits to the start of the message. Then, the interstitial checksum bits are added by inserting S zero bits after each F-bit fragment of the message (as padded thus far). If the final fragment contains fewer than F bits, it is left short but still appended with the full S checksum bits. Finally, the terminal checksum field is attached by appending K zero bits to the end of the message.
The following shows the padding process for [R,K,F,S] = [4,7,3,2] applied to a 12-bit message.
Original Message:
M M M M M M M M M M M M
After adding the Random Preamble Field
R
R R
R M M M M M M M M M M M M
After adding the Interstitial Checksum Fields
R R R S
S R M M S
S M M M S
S M M M S
S M M M S
S M S
S
After adding the Terminal Checksum Field
R R R S S R M M S S M M M S S M M M S S M M M S S M
S S K K
K K
K K
K
The length of the padded message is given by
Length of Padded Message = (R+M+K) + S*ceiling((R+M)/F)
Notice that there is no requirement preventing message fragments from spanning adjacent fields and, hence, a fragment could contain both preamble and message bits, both message and terminal checksum bits, or even all three. However, it would not be unreasonable for a particular implementation to require that each of the three fields, {R,M,K}, be integer multiples of the fragment length, F. Doing so could result in more compact and/or efficient hardware implementations.
The core of the BBC algorithm is a suitable hash function that maps message prefixes to codeword locations. The requirements placed on a BBC hash function are nowhere near as onerous as that placed on hash functions used for cryptographic implementations; thus simpler and much faster hash algorithms that are custom matched to the specific needs of a BBC codec are possible. The Inchworm algorithm is one such possibility.
Regardless of which hash function is used, and the particular manner in which it is used, the following notation will be used to indicate where within the codeword a mark should be placed: H(k,j). This means to hash the k-bit prefix of the padded message and return the location for the jth mark associated with that hash. All parameters are 0-indexed, meaning, for instance, that codeword locations are numbered from 0 to (C-1). If the j parameter is either 0 or omitted, then it refers to the first (and possibly only) mark location associated with that hash.
With few exceptions, the hash functions used in BBC implementations to date are based on the SHA-1 hash algorithm. The reason is nothing more than that implementations in the C programming language were readily available that could be easily modified. The specific version of the SHA-1 algorithm used was written by Paul E. Jones and copyrighted in 1998. Although the SHA-1 standard (FIPS Pub 180) can produce a message digest for any length message that is less than 264 bits, the Jones implementation works only with byte-level resolution. In order to hash message prefixes with bit level resolution, each bit in a message is translated into an 8-bit byte using the ASCII codes for '0' and '1', depending on the value of the bit.
The SHA-1 message digest that is produced for each prefix is mapped to a location in the codeword by reducing the low order dword modulo C (the codeword length). Some of the BBC implementations permit arbitrary codeword lengths of up to 232 while others, primarily those intended for real time applications, restrict the selection to being an integer power of 2 so that bit masks can be used instead of modular division.
The Inchworm algorithm is an extremely fast, incremental, and reversible hash algorithm that was specifically developed for use with concurrent codecs. The details of the implementation will be presented at the 2010 IEEE Military Communications Conference (MILCOM) and will be included here once that has occurred.
The encoder forms the actual codeword by starting with a codeword template and then adding marks to the codeword based on the hash of progressively longer prefixes of the padded message. The codeword template is simply an initial pattern that all codewords start with and could well be completely blank. However, the most common template contains a pair of bookend marks -- one mark at the first position and another mark at the last -- to help the decoder identify potential packets and to assist in compensating for oscillator mismatch between the sender and receiver.
Marks are added to the codeword template according to the H:B parameters of the codec, which merely states that each k*H-bit prefix of the padded message is run through a hash function and the output is used to place B marks within the codeword. This process is performed for each value of k from 1 through the minimum value needed to result in the entire message being used.
For example, say that a padded message that is 637 bits long is encoded using a 3:4 codec. The 3-bit prefix would be run through the hash function and the output used to place four marks in the codeword. Then the 6-bit, 9-bit, and so on prefixes would be used until eventually the 636-bit prefix would be used. Finally, the full 637-bit message would be used to place a final set of four marks.
The details of which hash function is used, how the prefix is fed into it, and how the output is used to determine mark locations is part of the protocol definition that must be accessible to all users beforehand. Since it has no security requirement, it may be made publicly available.
The initial codec implementations used SHA-1 as the hash function due primarily to it being readily available. Padded message bits were added to it one at a time by inputting 8-bit ASCII bytes to it - a '0' for a 0-bit and a '1' for a 1-bit. The mark position was determined by reducing the least most significant double-word of the resulting message digest modulo the codeword length. For simplicity, the codeword length was restricted to being a power-of-two so that a simple bit mask could be used. When additional marks were needed per hash block, progressively more significant dwords from the message digest were used, thus placing a maximum of five marks that could be generated per hash block. This approach is not particularly efficient, just relatively easy to implement.
While there is no requirement that the padded message length be an integer multiple of the hash block length, particular implementations may impose such a requirement. Furthermore, they may place additional requirements on the relationships between the parameters so as to simplify hardware implementation.
A generic encoder that supports all of the parameters described above can be constructed in a top down fashion. The high level description is given first.
Encode(Message)
reset_encoder();
codeword = create_codeword();
while (bits = get_next_block(block, message))
{
hash = update_hash(hash, block, bits);
for (b = 0; b < bits; b++)
insert_mark(codeword, get_mark_location(hash, b));
}
For simplicity, we are assuming that message, codeword, and block are all arrays having one bit stored in each element. In practice, implementing the encoder this way will consume significant amounts of unneeded memory, but conceptually it is perfectly viable and it will make our pseudocode much more understandable.
The concept here is very simple, but the use of C-style constructs may be confusing for non-C programmers. Also, this is meant to be pseudocode, so a number of details are left fuzzy. In particular, most of these functions need to retain information from one call to the next, such as how much of the message has been encoded thus far or the prior hash state; either that, or this information needs to be passed to each function at every call. We will address this issue down the road once we have identified exactly which information must be tracked. It's also assumed that each function has access to the current codec configuration; this can either be accomplished by making that information globally accessible or by packing it into a structure and passing the structure to each function. Doing the latter would also provide a reasonable vehicle for maintaining the necessary state information mentioned previously. For now, however, we wish to focus on the conceptual tasks performed by each of the functions.
The reset_encoder() function initializes all of the state information needed by the encoder. For now we will assume that this occurs and will deal with exactly what has to occur and how to do it later.
The create_codeword() function creates a codeword that is a copy of the chosen Codeword Template.
The get_next_block() function returns the length of the next block of bits from the padded message that is to be encoded. If there are no more bits, it returns zero and the loop is exited.
The update_hash() function adds the new bits in block to the hash of the message to this point.
The get_mark_location() function translates the hash output and extracts the indicated mark location from it.
The insert_mark() function updates the contents of the codeword so as to insert the new mark into it. This includes any encoder-side options such as Mark Width and/or Mark Growth.
Of these functions, the one that is most at the heart of the algorithm is get_next_block(). In Vanilla BBC it is very straight forward and all it does is return the next H bits of the message, switching to the terminal checksum bits once the message bits have been exhausted. The pseudocode for this basic version is shown below.
get_next_block(BYTE block[], BYTE message[])
{
h = 0;
while ( (h<H) && ((m<M)||(k<K)) )
{
if (m<M)
{
block[h++] = message[m];
m++;
}
else if (k<K)
{
block[h++] = 0;
k++;
}
}
return h;
}
Note that the value of m and k must be tracked from one invocation to the next, and thus these must be state variables that are maintained.
Adding support for the random preamble is extremely simple since all that is required is to feed those bits first. Of course, now r must be tracked as a state variable, as well.
get_next_block(BYTE block[], BYTE message[])
{
h = 0;
while ( (h<H) && ((r<R)||(m<M)||(k<K)) )
{
if (r<R)
{
block[h++] = random_bit();
r++;
}
else if (m<M)
{
block[h++] = message[m];
m++;
}
else if (k<K)
{
block[h++] = 0;
k++;
}
}
return h;
}
The only remaining component of this function is support for interstitial checksum bits. Because the interstitial checksum bits are not applied to the terminal checksum bits, this is a little more complicated. all that is required required conceptually is to ping pong back and forth between pulling bits the way that the function has to this point and pulling additional checksum bits.
get_next_block(BYTE block[], BYTE message[])
{
h = 0;
while ( (h<H) && ((r<R)||(m<M)||(k<K)||(s<S)) )
{
if ((r<R)||(m<M))
{
if (f<F)
{
s = 0;
if (r<R)
{
block[h++] = random_bit();
r++;
}
else if (m<M)
{
block[h++] = message[m];
m++;
}
f++;
}
else if (s<S)
{
block[h++] = 0;
s++;
}
else
f = 0;
}
else if (s<S)
{
block[h++] = 0;
s++;
}
else if (k<K)
{
block[h++] = 0;
k++;
}
}
return h;
}
The insert_mark() function nominally places a mark within the codeword at a specific position. However, it also places any additional marks needed to satisfy the Mark Width and Mark Growth requirements.
In order to accommodate the potential need to place marks outside of the basic codeword boundaries, the nominal codeword is offset by mark_width positions from the front of the memory and the memory is extended beyond the end of the nominal codeword by an additional (mark_width)*(C*mark_growth)/220). These limits provide a bit of margin and could be tightened if absolutely necessary.
The simplest way to implement these functions is to first implement a simple function to handle the mark_width codec parameter, but to do so as a passed variable. Then the mark_growth parameter can be handled by computing an effective width for each mark passed.
insert_wide_mark(BYTE codeword[], int location, int
width)
{
for (bit = location - (width-1)/2; bit <= location +
W/2; bit++)
codeword[offset+bit] = HI;
}
insert_mark(BYTE codeword[], int location, int width)
{
width = (C*W*location)<<20; // Note: Be careful of
overflow and/or roundoff.
insert_wide_mark(codeword, location, width);
}
The decoder extracts messages from a packet by performing a guided search of the tree representing the entire padded message space, expanding only those branches for which the requisite marks are contained in the packet. An important part of the pruning process is for the decoder to leverage the fact that all checksum bits always have a value of zero. While, in theory, the decoder could choose not to exploit this distinction and simply treat them as normal data bits and pass all extracted messages, including those containing non-zero checksum bits, to the next higher layer in the stack, doing so can significantly increase the decoder workload as well as the workload of higher layers. In particular, note that failing to discriminate against messages having non-zero interstitial checksum completely defeats their purpose, which is to prune hallucinations throughout the decoding process instead of just at the end.
Most conceptual descriptions of the decoding process imply a breadth first search along the following lines:
To extract all of the padded messages that are covered by a given a packet (which can be considered nothing more than a list of mark locations), use the following algorithm: start with an empty list of padded message prefixes (which can be thought of as the list of 0-bit prefixes that are covered by the packet, but this is semantics). Generate the next prefix list by taking each prefix in the current list and adding all possible values for the next block of bits and retain only those that are covered by the packet. Repeat this process until the list consists of full-length padded messages, which are thereby the only ones covered by the packet.
This description lends itself well to recursion as follows:
message_list = decode(packet, NULL, 0);
where decode() is defined as follows:
BYTE **decode(BYTE *packet, BYTE *prefix, int bit)
{
if (NULL == prefix) // Initial Call
{
message_list = NULL;
bit = 0;
}
if (bit < padded_message_length)
for (pattern = 0; pattern < 1<<H; pattern++) // For
each possible pattern of the next hash block
{
block = next_block(bit, b); // may be NULL if next
pattern has non-zero checksum bits.
if (found_marks(prefix, block) // returns FALSE if
block is NULL
{
next_prefix = concatentate(prefix, block);
decode(packet, next_prefix, bit+B);
}
}
else
message_list = add_prefix_to_list(message_list,
prefix);
return message_list;
}
Keep in mind that, while the above looks like C code, it is really pseudocode and therefore required housekeeping tasks are neglected. Relevant to the above code, passing NULL as the prefix parameter in the original call simply means to start with an empty prefix. The concatenate() function can be written to trap this condition and deal with it. Similarly, the message_list starts out as an empty list and the add_prefix_to_list() function can deal with this. The next_block() function is responsible for generating the next pattern for the present hash block and trapping those that would contain non-zero checksum bits.
While the recursive algorithm resembles the breadth-first description, the nature of recursion will result in this being realized as a depth-first search. As it turns out, performing a non-recursive depth-first search has significant benefits from the standpoint of implementing a real-time, hardware-based decoder. Perhaps the biggest advantage is that the decoder only requires a fixed amount of memory.