There is also a study of some well known code and how many there can be before the coding scheme runs out. This was published in the "American Scientist" magazine, Vol 93, Jan-Feb 2005. It covers the following coding schemes:

1. Internet account IDs
2. NY Stock Exchange Ticker Symbols -- up to 3 Uppercase letters -- 26+26**2+26*3 possible

3. Universal Product Codes -- bar codes -- ( UPC )-- 12-digit until January 2005, and then 13-digits.
4. Global Traded Item Numbers (GTIN)
5. European Article Numbers (EAN)

6. Biological Species -- Two Latin-like words
7. The Chemical Elements -- One uppercase letter + option lower case letter. (I had to program these while working for ICI in the 1960's)
8. Organic Chemicals -- Complex coding.
9. Internet Assigned Number Authority IANA names for countries -- two ASCII letters
10. Radio Call Signs -- 3..4 Capital letters -- KVCR, KFROG, ...
11. Telephone numbers -- 10 digits (in the USA).
12. Social Security Numbers -- 9 digits in the USA
13. Airport codes (IATA) -- Three letters.
14. Names of Horses -- 2..18 characters ( letters plus space, period, and apostrophe).

We look for the best technology to represent our data. Each data flow in a DFD has many ways to be implemented. It could be a phone call, a memo, a signal between devices, or a the sending of a record of data between parts of the system. Each flow from an external entity into your system needs an input device. Each store needs a storage device. Each flow between processes can be internal to a program or use a network. And each flow out to an external entity will use an output device. Choosing a good device and technology can make a system fly rather than crash. So you need to know about the options. The hardware options were covered in [ a2.html ] earlier. When the data is digital we still need to choose how to encode different things. Encoding data is a return to Physical Design from Logical Design. On the other hand drawing up a logical model of data is all about ignoring the actual encoding of the data.

Reminder -- use UML Classes to model logical data records

1. Draw a class box with two compartments (suppress the third compartment if using a tool).
2. Put the record name in the center of the top compartment -- the class name.
3. List the attributes inside the second compartment -- these are the elements.
4. Example:

Special Encodings

Encoding Data Elements

There are a number of well known ways to encode data elements.

Common Numerical Codes

Roman

Humans tend to use a notation for numbers based on the number of fingers on a hand. In fact the word digit comes from the word for finger. In Roman, times the 'V' stood for a hand (5= one thumb + four fingers) and the 'X' was two hands (one up one down) or 10 fingers.

Decimal

From the Arabs we have leaned the "decimal" notation. We encode the digits as 0,1,2,3,4,5,6,7,8,9. Then we can represent any whole number by string them together:
1. digit::=0..9.
2. number::= one or more digits.
3. 987 = 100*9 + 10*8 + 1*7.
4. For number n, digit d, value( n d ) = 10*value(n) +d.

   Binary

   Computers use binary (you can find examples of this in Ancient China and Leibniz). This has two digits: 0, 1. So:
5. 110011 = 2**5 + 2*4 + 2**1 + 2**0 = 32+16+3 = 61.

   In about 1945 Shannon defined

6. bit::="Binary digIT", is either 0 or 1.
7. binary_number::= one or more bits.
8. For binary_number n, bit b, value( n b ) = 2*value(n) +b.

   Octal and Hex

   This has resulted in many computer people being able to recite the powers of two up to the highest address on their favorite machine. However, calling out or typing 20 binary digits is a little inefficient, and decimal notation disguises the binary format (which is often significant) and so computer people tend to use base 8 (octal) and base 16 (hexadecimal) notation:
9. nibble::= 4 bits.
10. byte::=2 nibbles.

    Nibbles are written and spoken using the hexadecimal digits, 0(=0000),1=(0001),2,3,4,5,6,7,8,9,A,B,C,D,E,F (=1111).

    Signed Integers

    In scientific computations integers are encoded using binary typically with 8, 16, 32, ... bits. One extra bit indicates whether the number is negative or positive.

    In commercial systems it was common to find numbers encoded using

11. BCD::="binary coded decimal".

    Here a number like 987 was encoded by three decimal digits each represented in binary:

12. 1001 1000 0111

    This wastes some bits but is very convenient for important things like dollars and cents.

    Real Numbers

    Real numbers (measurements) are encoded using "floating point" where a number has two parts called the mantissa and the exponent, both encoded in binary. The value is then
13. mantissa * 2**exponent

    Floating point works well when we need a wide range of values and can put up with larger errors on the larger numbers.

Standard Character Codes

At one time each manufacturer had its own binary code for characters. This continued up to the 1980's

In the 1960's the American standards people proposed what has become the standard 8 bit coding for characters -- ASCII

1. ASCII::="American Standard Code for Information Interchange".

   ASCII covers all the characters needed for American needs, but has become the de facto standard on the Internet, and whenever data needs to be shared. The International Standards Organization treats ASCII as a specialized code for use in America. In the UK, the American "#" becomes the symbol for the British pound. Each European country has its own special symbols.

   IBM tried to create its own standard -- an Extended Binary Coded Decimal code named EBCDIC. This will disappear with the last mainframe.

   Recently, a new standard -- Unicode -- has been created that covers just about every character in every alphabet in the world. This is a 16-bit code. ASCII and the ISO codes appear within it.

   The Web uses HTML and HTML has introduced a number of special "entities" for showing non-ASCII characters like Σ and α. These are given numbers and encode in HTML like this:

2. "&" digit digit digit ";"

Keys

A key is an item of data that is used to uniquely define a single element in a file, database, or table. These are typically a fixed number of characters.

Sequence numbers

Example: Number of a student on roster.
1. Numbers assigned in a specific order -- typically when created.

   Block sequences

   Example: CSUSB Course call Number
2. Blocks of numbers given to different parts of the organization to allocate (in sequence) to data records.

   Alphabetic Abbreviations and Mnemonics

   Example: States(CA, AL,...), IANA and DNS countries(uk, tv, ru, ...), IATA (LAX, ONT, LHR, MSP, ...) Abbreviation for a department teaching a course -- CSCI PHYS MATH ENG. Abbreviations for buildings on campus.
3. A string of letters is chosen to identify an entity or a group of entities of a given type. A few letters stand in for a word or phrase

   Arbitrary Systematic Codings

   Example: Library of congress subject classification, Dewey Decimal system for books. The Assoc for Computing CCS system for computer science. Linnaeus's technique for species.

   Significant subgroups

   In many cases a data element is actually made up of smaller elements each with their own coding.

   Digit Groups

   Example: Zip codes(92407-1133), phone numbers((909)-537-5257),..., SSN, URLs. Different groups of digits/characters in the data are themselves coded data. For example in a 9-digit ZIP-code the first digit determines a geographical area, the next three the town, and the 5th digit a post-office. The next 4 digits identify a delivery point.

   Derived Codes

   Example: My UK Driving license number, CSUSB Library call numbers, Subscriber codes for magazines, Rooms on campus. Mixes different coded data into one element

   Ciphers

   Example: Spoof at ICI (a number added to the paint sales). DES. PGP. ... Numbers are disguised for security or mnemonic purposes Passwords should be encrypted as soon as they are entered and never stored without salting and hashing!

   Actions

   Example: A=Add, D=Delete, ..., The 50+ actions that the 'vi' editor has built in to it, Mnemonic codes in assembler. Codes that represent actions. Transaction codes.

   Self-checking Elements

   Example: 9s remainder and 11s remainder check digits. Uses an added digit or character calculated from the rest.

Encoding Compound data

Elements usually occur together in logical grouping. The problem to be solved is to design an efficient way to combine them so that the data can be extracted in only one way. Extracting data elements from compound data is called parsing. When there is more than one way of parsing a compound data group then the coding is said to be ambiguous. Ambiguous Encodings are bad encodings.

There are four classic ways of encoding these. We also have the new markup notations:


1. Fixed Length fields: Phone number.
2. Delimiters and counters: tab delimitted spread sheet.
3. Complex Syntax: C++ programs.
4. Marked Up Text: HTML, XML, ...



Record Structures

In a record structure a number of fields are defined, each with a given length (bits or bytes). Each field has a name and its own encoding. A very popular technique in RAM and in Data Bases. Record structures rely on each element being a fixed length. And this in turn gave us one of the most successful bugs (so far) in the history of computing: the Y2K Bug. Just about every system was at risk of breaking down when a 2 digit field could no longer handle years greater than 1999. And just about all of these problems were found and fixed before the date arrived. Business as usual, computer people had to work hard and late into the night to make computers do what they were supposed to do.

Delimiters

A common kind of data is the string. It can have any length When the data does not have a fixed length the end can be marked by a special sentinel character -- a delimiter. In programming languages for example we indicate the start and end of a string by using a quotation mark.

Count Fields

Another technique is to add a field indicate the length of the following data element -- an encoded counter or integer. Humans do not find this as easy as delimitted data

Simple Syntax

A very simple way to place several variable length fields into a single string is to make sure that the first character of each field can not be a character in the previous field. A simple example would be to choose alternating digits and letter encoding.

Markup Languages

In recent years there have been a lot of markup languages defined for different purposes. The idea is to have explicit identification of the parts of the data. Typically something like

 <name><first>Richard</first><initial>J</initial><family>Botting</family></name>

is a piece of text with added "tags" that indicate the meaning of the parts. In a [ Record Structure ] (above) the "tags" are not needed because their sequence is known and the lengths are fixed (or at least predictable). Thus we get an encoding that is guaranteed not to be ambiguous, is to some extent easy to read, and is somewhat inefficient.

RTF -- Rich Text Format

Here the tags indicate the appearance of the text. Probably developed with early word processor software. Still a format used with MS Word.

SGML -- The Standard Generalized Markup Language

IBM defined SGML so that you could created and define tags for any purpose. It is an amazingly difficult encoding to use.

HTML -- The HyperText Markup Language

HTML is a specific application of SGML defined to describe and link pages on the world-Wide Web. It has gone through half-a-dozen versions. A new one stays within the XML (next) conventions.

XML -- the eXtendable Markup Language

HTML describes the appearance of pages. XML tries to describe the meaning of data not its appearance. It has a very simple basis using

 		<tags>

 		</end tags>

to delimit data. Tags can also have attributes:

 		<certificate type="participation">Unix Training</certificate>.

XML also allows some tags to be unpaired and these are shown like this:

 		<endless tag attributes... />

XML documents can be parsed fairly easily.

For each application that uses XML must have a DTD -- Document Type Definition published that defines the structure of the data -- what tags can appear inside others. Defining a DTD takes a significant amount of work. But once defined you can use tools to check validity, ...

. . . . . . . . . ( end of section Markup Languages) <<Contents | End>>

Complex Syntax

Complex syntax gets us into natural and artificial languages. It is rare that we need to express natural data groupings using complex syntax. When we do we can use a extension of the syntactic meta-languages like Backus-Naur Form (BNF).

In computer science most of our knowledge about linguistic design has been put into designing programming languages. Programming languages are the most complicated schemes for encoding a domain in existence. There are hundreds of them. For more take a CSCI Programming Language class like our CSCI320 [ ../cs320/ ] (Advert).

. . . . . . . . . ( end of section Encoding Compound data) <<Contents | End>>

Experience -- coding data in the ICI Infra-Red Spectrum Analysis Program.

. . . . . . . . . ( end of section Special Encodings) <<Contents | End>>

Guidelines for encoding data

1. Make your codes -
   
   1. Concise
   2. Expandable
   3. Stable
   4. Unique
   5. Sortable
   6. Meaningful
   7. Single Purpose
   8. Consistent
   9. Clear -- Don't allow digits and letters in one field. They look too alike: (0=O, 1=l=|, 2=Z, 5=S, 6=b, 8=B)
   
   
2. Use standard codes and technologies whenever possible!
3. Collect input automatically if at all possible.
4. Get the input where it is available.
5. All data storage needs back up and archiving.... but for how long?
6. All output needs data control, security, and destruction.
7. Who needs dead trees? Paper data is dead data.
8. All stored or transmitted data implies a security problem. All data needs some kind of security -- how much and at what cost?
9. Design I/O with care and with the help of the users.

Information theory and combinatorics

An elegant theory of coding data and signals. It shows that you can measure the information needed for a given purpose and calculate the maximum rate at which data can be sent through a given channel using the same measure: bits. Do the math. MATH272+MATH262.

Reference and Online Resources

Universal Product Code

I don't expect you to understand UPC but if you are interested in these ubiquitous bar-codes see [ Universal_Product_Code ] for the details and history.

Samples of Syntax Definitions

My [ http://www.csci.csusb.edu/dick/samples/ ] define a large number of sophisticated coding schemes including programming languages and meta-languages.

ASCII

For reference purposes see [ comp.text.ASCII.html ]

Markup Languages

For reference purposes see [ Mark Up Languages in index ] (my notes).

HTML

[ ../samples/comp.html.syntax.html ]

XML

[ ../samples/xml.html ]

XML reference

1. Robert Eckstein
2. The XML Pocket Reference
3. O'Reilly ISBN 3692082709 1999
1. Up to date reference [ 9780596100506 ]

. . . . . . . . . ( end of section XML) <<Contents | End>>

Review Questions

1. When did changing the coding of one element become important in CSUSB and the recoding take more than 6 months to complete?
2. What is IANA is and what does it do?
3. Define: ASCII, Unicode, BCD, EBCDIC.
4. Parse the following data strings -- label the parts:
   
   1. CSCI201-02
   2. http://csci.csusb.edu/dick/cs372/d2.html#Hints for encoding Data
   3. rbotting@csusb.edu
   4. telnet:139.182.151.222
   5. LOL
   
   
5. Take the above parsings and express it using a plausible XML syntax. For example the first might be

    	<section><department>CSCI</department><cnumber>201</cnumber><sectionnumber>02</sectionnumber><section>

6. How many ways can you encode a date?
7. How many ways can you encode a time on a given day?
8. How about encoding a time on any day....
9. Research: How does the California DMV assign number plates? Can you have an obscene vanity plate? How can California enforce this rule?
10. Compare doing the same calculation in Arabic, Roman, and Binary:
    
    1. 32 * 16 = ?
    2. XXXII * XVI = ?
    3. 100000 * 10000 = ?
    
    
11. Count from 0000 to 1111 in Binary, and in Hexadecimal.
12. Visit my office and figure out how I've encoded the day of the month in it.