CS 12 -- Lab 8

We seek to write code that does a bit of the grunt work for data compression. Given a specific encoding where symbols are represented by a variable number of bits, we want to take a string, encode it, decode it, and compare it to the original. Any compressor/decompressor must perform these steps, and we particularly want to focus on how to manipulate data at a bit level to perform this encoding/decoding.


Bit manipulation operators

In order to manipulate individual bits, Java provides a number of useful operators that you can use on integer values. Each of these operators manipulates the bits of an integer on a bit-by-bit basis. Here is a listing of the basic operators and how to use them:

These operations can be used to set or test any single bit or group of bits. You will need to set bits to encode a given output, and test bits to decode them.


Your assignment

Assume a very simple encoding, based on a brutally simple model. Specifically:

  1. The character e is encoded as the bit 0.
  2. Any other character is encoded as the bit 1 followed by the least significant 8 bits of the char value.

You must write a SimpleCode class. It must contain two public methods:

  1. public static int[] encode (String original);

    Given a String, encode each of its char elements using the encoding given above. Store the result in an array of int, where each integer contains the next 32 bits of the encoded representation.

  2. public static String decode (int[] encoded);

    Given an array of int that contains an encoded representation, decode the sequence of symbols and return it as a String.

The main method of this class should pass a string into the encode method, and then pass the result of that call to the decode method, and finally compare the two.

In order to facilitate the organization of the bits into a stream, you should use the BitStream class. It will store a arbitrarily long sequence of bits into an array of int, making your job here much easier. You can grab this class at:

~sfkaplan/public/cs12/BitStream.java

What you must submit

Once you have written and tested the various classes, you must use the cs12-submit command to submit them. Submit this assignment as lab-8 when you use the cs12-submit command.


This assignment is due on Sunday, April 25th, at 11:59 pm.

Scott F. Kaplan
Last modified: Sun Nov 5 22:48:52 EST 2000