COSC 159 - ASSIGNMENT #1 Error-correcting codes Due date: Monday, Feb. 2, 1998 Because the music is digitally recorded with error-correcting codes, a compact disk player can produce beautiful music even if the disk has a minor scratch on it. The way such codes work is that data read from the disk is compared to a fixed set of "code vectors" (we'll represent these data and code vectors by lists containing sequences of 0's and 1's). If the data read is not exactly equal to some allowable vector in the code, then we know there was an error in reading the data. In this case, we can attempt to correct the data by using the code vector which is closest to the data vector - that is, a code vector which has very few differences from the read data. The number of positions in which the data vector and the code vector differ is called the "Hamming distance" between them and we seek a code vector with Hamming distance as small as possible. Note that a distance of zero would mean the two vectors are equal which would happen when there was no error in reading the data. GOAL: Write a Lisp function 'distance' which takes two 0/1-vectors (lists containing only 0 and 1) of the same length and returns the Hamming distance (number of differences) between them. Thus, (distance '(1 1 0 1 0 0) '(1 0 0 1 1 0)) would return the value 2 since these vectors differ only in the second and fifth positions. Then, use this function to write a function 'closest' which takes a 0/1-vector and a list of such vectors (called the code list) and returns the closest vector in the code list to the given vector. For instance, (closest '(1 1 0) '( (0 1 1) (1 0 0) (0 0 0) ) ) should return (1 0 0) because that is only distance 1 from (1 1 0) whereas the other two vectors in the list are distance 2. A sample code list can be found in the file ~mikes/159/codelist.lisp on studsys. METHOD: Writing the function 'distance' is a good warmup and will also be a useful function to have when writing 'closest'. The body of 'distance' should be a cond expression which deals with the various cases such as first argument empty, first elements of each argument equal to each other, etc. In each case, you decide what the appropriate answer is for 'distance' in that case. The List-Processing Examples section (p. 49) in the text gives several examples of the type of recursion used to process lists in Lisp. Other simple examples can be found in the directory ~mikes/159/clisp on studsys. DEVELOPMENT: It's probably a good idea to put your function definitions into a file (with your favorite editor) and then load them into Lisp. This allows you to make changes more easily than if you just type them at the command line. Once you have the Lisp code in a file (say myfuns.lisp), start clisp by typing clisp and then, in Clisp, type (load "myfuns.lisp") This is a built-in function which reads a file as a side- effect and returns T (true) if everything loads success- fully. Once you are in clisp, you can edit your file (without having to leave clisp) by typing (ed "myfuns.lisp") This seems to automatically invoke the vi editor. EXTRA: As mentioned in the course syllabus, earning a grade of A or AB generally requires some extra effort beyond the basic assignment. You are welcome (and encouraged) to do anything that sounds interesting and requires that you learn more about programming in Lisp. For example, you could try and write a version of 'distance' which handles vectors (lists) of different lengths. See problem 2.4 on page 66 of the text for some other ideas. If you are unsure whether or not some particular extension would be appropriate, just ask me. HAND IN: A listing of your program (with appropriate comments) and several sample runs demonstrating features of your program. At the very least, I'd like you to hand in the results of running closest on the vectors '(1 0 0 1 1 0 0), '(0 1 1 0 0 1 0), and '(1 0 1 1 1 0 0) with the supplied code list (from ~mikes/159/codelist.lisp). Be sure to demonstrate any special features which you may have added. You can hand in paper copies or email these things to me.