About QCode:

QCode, written by Jason M. Chu of Boston University, is an exhaustive search engine for q-ary codes.

Background:

The first assignment for one of my engineering courses at Boston University, Error Control Codes (SC561, Fall 2001), is to determine whether a set of codewords exist given the code length, distance, radix, and the number of codewords required. Without knowing how to construct generator matrices at that time, it took quite a long time to accurately figuring out a set of codewords, even if the length was relatively short.

So, instead of searching my eyes off, I've decided to write a program to do all the tiring works for me. The writing of the program itself took only about 15 minutes and the codewords searches were done in a matter of seconds. Overall, this is a good investment in time.

The first QCode was programmed in GNU C++. The current version was developed in Microsoft Visual C++ .NET.

 

 

About Q-ary Codes:

A q-ary code is a given set of sequences of symbols where each symbol is chosen from a set of Fq = {l1, l2, ... lq} of q distinct elements. The set Fq is called the alphabet and is often taken to be the set Zq = {0, 1, 2, ... q-1}. However, if q is a prime power (i.e. q = ph for some prime number p and some positive integer h) then we often take the alphabet Fq to be the finite field of order q. 2-ary codes are called binary codes; 3-ary codes are sometimes referred as the ternary codes.

(Text obtained from Raymond Hill's "A First Course in Coding Theory")

 

The Algorithm:

There is no complex algorithm in QCode. The program simply does what a normal human being would do to identify codeword set members -- go through all the possible codewords one by one and filter out everything that doesn't belong. That is, take out any codeword that doesn't meet the minimum distance requirement.

There are two different representations of codeword: numerical and symbol-carrying (QCode has both implementations). For the numerical format, codewords are represented as a long integer. Whereas for the symbol-carrying format, codewords will be in the form of a character array or string.

For example, for the radix-2 codeword: 0110101, the representation will be:

  • Numerical: Decimal 53
  • Symbol-Carrying: {'0', '1', '1', '0', '1', '0', '1'}

Regardless of the representation, in order to determine the distance the program will compare two codewords digit by digit.

 

The Program:

QCode is a dialog-based exhaustive search engine. To identify the correct codewords, the program simply loops through every possible codeword and determine whether or not it meets the minimum distance requirement. The search result will be added to a list control object in the dialog. In addition, the program will determine the total number of possible codewords and whether the codeword set is unique.

The user will provide to the program the codeword length (n), the minimum distance between codewords (d), and the radix (q).

Numerical Search:

Codewords are represented as long integers. The program will search through all the codewords from 0 to qn - 1. The digits of a codeword is obtained by performing a combination of division, modulus, and exponent arithmetic functions. To add the search results to the list control object, all codewords must be converted into strings.

Advantage:

  • The program may loop through all the codewords very quickly since moving from one codeword to the next is simply incrementing an integer counter.

Disadvantage:

  • The very time consuming Math class pow() function was used for exponential computations.

Symbol-Carrying Search:

Codewords are represented as a character array or string (the CString class may be used in this case). The program will search through all character combinations from an array where all digits are 0 to an array where all digits are q-1. To obtain the next codeword, the program will have to increment the last digit of the current codeword. In the case when the digit has reached the value of q, the algorithm will trigger a "carrying-over" event and increment the preceding digit until no more carrying-over is possible (i.e. the end of the search). This may be done easily with a single recursive function.

Advantage:

  • Since the resulting codewords are already in a character array format, they can be added directly to the list control object without conversions.

Disadvantage:

  • The fact that the codewords are represented in an array requires the program to have additional loops within the search in order to obtain all the digits.

Note: On average performance, a symbol-carrying search is usually slightly faster than a numerical search.

Timing:

The GetSystemTime() function (time.h) was used to obtain the current system time accurate to the degree of milliseconds. A simple calculation between the time differences from the beginning to the end of the search will determine how much time exactly does the entire searching process takes.

Uniqueness:

A set of unique codewords means that the search result is the only set of codewords that satisfies the user's parameters. In order to determine whether the result is unique or not, the program will simply look at whether or not the first and the last resulting codewords are complements of each other. If so, the code is unique.

(In the case of non-unique search results, taking the complement of all the resulting codewords will alter all the members in the set but they will still satisfy the minimum distance requirement.)

 

Statistics (Timing Analysis):

The followings are the calculated averages of 10 independent trial results.

1. by codeword length: constant d, q:

2. by radix: constant n, d:

3. by distance: constant n, q:

* Timing will vary according to the speed of the processor unit.

 

Screenshots: