Linked List Data Encoding Method and Control Apparatus for a Visual Display

Visual display apparatuses such as cathode ray tube terminals, impact and thermal printers, laser beam raster scanned displays and the like can have a number of hardware and software specialized functions which describe the displayed image besides the normal characters. For example, in a CRT terminal the characters can be blinking, half-bright, inverse video or underlined. The characters may be protected so they may not be altered. In addition, the display structure itself may be alterable. All three of these types of information: hardware display parameters, software parameters, and display structures are examples of information which must be embedded in the display text without causing blanks to be inserted in the visual display.

A typical solution is to use a wide display character which has appended to it one bit for each function. Each additional bit represents a different control function. Referring to FIG. 1, there is shown a typical method wherein parallel definition of display parameters is utilized. Such a method would require, for example, if ASCII were the coding utilized, the width of the characters to be 7-bits. One bit in addition would be required for each enhancement mode. Six enhancement modes would require an additional six bits for each character displayed. If one were to add a protected field feature, the total required width necessary would be 14 bits per character. This would require a display memory having a capacity greater than or equal to 14 bits per character. If a particular enhancement feature, for example, underlining, were desired, the enhancement bit would be on for characters displayed with underlining and off for non-underlining. Therefore, whether an enhancement feature is used or not, the extra bits of display storage are required.

Referring to FIG. 2a, there is shown a second method having advantages over the first. In this second technique every character is made 8-bits wide. The characters are of two types: 8-bit data characters and 8-bit control characters. Data characters are directly displayable whereas control characters indicate a change in mode of enhancement or other control function.

Referring to FIG. 2b, assume it is desired to display the word "FIELD" and to underline each character of the word. The traditional technique discussed above would add a bit to each of the displayed data characters indicating that that character is to be underlined. In contrast, the second method would precede the displayable word in the character stream with a control character to "start underlining." This control character would then be followed by the five display characters. After the final data character to be displayed another control character indicating "stop underline" would be sent. It can be seen that the second method requires data storage in the memory only when enhancements are actually used. The second method has advantages over the first in that the control characters are needed only if the current control state is to be changed. No unnecessary memory is required. Further, the number of control functions is not limited.

FIG. 1 illustrates an encoding method heretofore known in the art utilizing parallel definition of display parameters wherein extra bits of display storage are required whether an enhancement feature is used or not.

FIGS. 2A and 2B illustrate a novel encoding method wherein data representing figures to be displayed and control functions are configured as 8-bit data and control characters.

FIG. 3 is a block diagram of a preferred embodiment for use with a CRT made in accordance with the invention.

FIG. 4 illustrates a manner of storing data in a memory in a linked list for use with the embodiment of FIG. 3.

FIG. 5 illustrates the interrelationship between data blocks, links, and a visual display per scanned line.

FIG. 6 shows the relationship of FIGS. 6A to 6D which together are a detailed schematic diagram showing commercially available hardware for implementation of the preferred embodiment of FIG. 3.

FIG. 7 illustrates the coding sequence of the bus cycle flip-flops of the preferred embodiment.

FIG. 8 illustrates a method of encoding data for use with the preferred embodiment.

Referring to FIG. 3, there is shown a display apparatus which reads characters from a random access memory 6, accesses data via input register 43, buffers them in 80-character shift register 12 and 14, and sends them to selector register 16 and then to character dot generation circuitry 18 which drives display device 200. The system responds to interrupt set signals 2 and vertical sync signals 4 from Timing and Control Circuitry 20 within character generator 18. Interrupt set signal 2 indicates that a new line of figures to be displayed is to be fetched from the terminal memory 6. Vertical sync signal 4 indicates a beginning of a visual display device scan. Interrupt set signal 2 triggers this system to access 80 displayable characters from memory 6 via a terminal data bus 10. The data is placed into one of two 80-character buffers 12 and 14. The buffer which is not being loaded by the system is being rotated at a 2.34 MHz rate and supplies one character for every nine dot positions being scanned across the face of a display device 200. From the system a character may go, for example, through the character generator 18 to a parallel to serial converter and finally to a cathode ray tube monitor or the like. If the character position is, for example, 15 scan lines high, the 80-character buffers are rotated fifteen times before a switch to a new displayable line is signaled by the toggling of an even/odd line 19 from the timing and control board circuitry 20.

This cycle repeats with the two 80-character buffers 12 and 14 ping-ponging, the first buffer refreshing while the other loads from the terminal memory 6, and then their roles reverse.

Referring to FIG. 3, control and data characters are input by entry means 202 such as, for example, a keyboard and stored in the terminal random access memory 6 in descending memory address order. The first character fetched is, for example, at an octal address 37777, shown 37777.sub.8 in FIG. 4, which is the highest or most significant memory address in the terminal. The next character is 37776.sub.8, etc.

Referring to FIG. 3, at the beginning of a display of a page the terminal memory address register 22 is set to location 37777.sub.8. A data control 8 accesses data characters, decrementing address register 22 after each character and executing the following display and control functions: LINK, wherein two characters are fetched from the terminal memory and become a next location address from which data is to be read. END OF LINE, wherein the remainder of a line to be displayed is written with blanks. END OF PAGE, wherein the remainder of a page to be displayed is written with blanks. FLAG, which is used for protecting data fields. DISPLAY ENHANCEMENT, wherein the control system uses one of the display enhancement bits, an INVERSE VIDEO bit, and passes it on to the Timing and Control Circuitry 20 along with characters to be displayed. CHARACTER, wherein a 7-bit code, for example ASCII or the like, represents 1 of 128 characters to the character generator means 18. Eighty displayable characters per line are accessed, after which data control 8 turns off and awaits a signal from Timing and Control Circuitry 20 to start a new line. After 24 lines have been fetched from the terminal memory 6, the cycle repeats with the terminal memory address register 22 being set again to 37777.sub.8.

Referring to FIG. 8, there is shown a novel encoded instruction scheme for use with the embodiment of FIG. 3. Assume a visual display device is scanned one whole frame every 1/60th second. During this time data characters and control characters are retrieved from the memory 6. As each 8-bit character is accessed, address register 22 is decremented. If the character is a display character, a character counter 26 is incremented. This keeps track of the remaining number of characters to be accessed from the memory 6 of a line to be displayed. However, if the character is a control character, the address counter 22 is incremented but not the character counter 26. Eight-bit characters continue to be accessed from memory 6 until 80 display characters have been accessed. Since control characters don't count in this accumulation, the number of control characters is variable.

The problem of decoding the novel encoded instruction set shown in FIG. 8 is neatly resolved with a priority encoder and decoder. Referring to FIG. 3, the data in register 43 goes into a priority encoder 46, which may be a Texas Instruments type 74147 integrated circuit, or the like. Encoder 46 has the characteristic that a 3-bit number 47 which comes out represents the highest bit position input which has a zero. The 3-bit number 47 goes into a decoder 48, which may be a Texas Instruments type LS 138, or the like. The result is that one pin of the decoder 48 goes low depending upon which type of character was fetched from memory. Thus, if the character fetched were an END OF LINE function, the number 5 output of the decoder 48 would go low. If the data were an ASCII character, the number 7 output would go low.

Referring to FIG. 4, data is usually stored in terminal memory 6 in a LINKED LIST. A link may be, for example, a 2-character control sequence, as shown in FIG. 4, which is interpreted by the data control 8 to change the terminal memory address of the next character to be fetched. The links allow the terminal memory 6 to be organized and used in a uniquely efficient manner and allow the tying together of data representing displayable lines of a visual display scan into displayable pages.

Referring to FIG. 5, the first two locations fetched, 37777.sub.8 and 37776.sub.8, are a link to the first 16-character block of information stored in terminal memory 6. In this first block of a line are links to the next block of that line and a link to the first block of the previous line and the next line.

Referring to FIG. 6, as the 24th character row of a visual display device is scanned a short vertical sync pulse 4 is received by address counter 22. This resets the address counter 22 to 37777.sub.8 and resets an END OF PAGE flip-flop 24 within the Data Control 8.

At the same time, the Interrupt Set signal 2 clears the character counter 26 to 0.

The output of the character counter 26 is detected by the Data Control 8 as not being equal to 80. If a DMA on flip-flop 28 is set, then flip-flop 28 goes high and a bus cycle is started.

With a dynamically allocated display structure to which there is simultaneous access by more than one process, a lockout procedure is required. The shape of the structure must be changeable without destroying the continuity of other processes' access. With the linked list memory structure employed, the Data Control 8 picks up characters from the terminal memory 6 at regular intervals. A processor may, for example, be changing the structure of inserting and deleting lines. If the processor, for example, would start to change a link character and the data control 8 would try to use the link, it would find one new character and one old one. This would errantly point the data control 8 off into memory, causing a flash on the screen. By turning the terminal bus control 30 off this flashing is minimized. The processor turns the bus control 30 off before changing a link and turns it on again after the change by means of flip-flop 28. Flip-flop 28 is clocked by a strobe signal 29 from a processor.

The bus cycle circuit 30 has three flip-flops, 32, 34 and 36. Referring to FIG. 7, the first flip-flop 32 is set when flip-flop 28 goes high and the flip-flops have a combined state of 000. When flip-flop 32 goes high, this is ANDed with two bus pins, BUSY 100 and PRIORITY IN 101. If these are both high, this indicates that the control apparatus may take control of the bus. Referring again to FIG. 6, it does this by setting flip-flop 34. This sets the bus signal BUSY 100 low through a tri-state gate 102.

The bus cycle flip-flops are all clocked off the trailing edge of a bus clock signal 42. After flip-flop 34 goes high, the combined state 110, shown in FIG. 7, flip-flop 36 is set. This enables a REQUEST signal 38 on the bus. If the logic is executing an END OF PAGE or END OF LINE function, the request signal 38 is held off.

The terminal memory 6 decodes its address and starts a timer upon receiving REQUEST 38. It immediately sets a WAIT signal 40 low to indicate that the REFRESH control apparatus should wait for the memory access time. When the memory's timer times out, it sets the WAIT line 40 high and the REFRESH apparatus proceeds to reset flip-flop 32. At this moment data is clocked off the data bus into the 4-bit registers 42 and 44 of input register 43. If the function being executed were an END OF LINE or END OF PAGE, however, a 1-bit is inserted in bit 4 by priority encoder 46, which amounts to loading in of a "blank" character when interpreted by character generator 18.

The terminal bus control logic 30 resets flip-flops 34. This takes REQUEST 38 off the bus. The terminal memory 6 will discontinue output of data when it sees this.

Two hundred nanoseconds later, the address is taken off the terminal bus 10 as flip-flop 36 goes low. The terminal bus control 30 has now completed a six-state sequence, as shown in FIG. 7, and is ready to start over.

If the function decoded were a LINK, a link flip-flop 50 is set. On the next fetch from the terminal memory 6, the clocking in of data into the input holding register 42 and 44 is disabled by the link flip-flop 50 and, instead, data is loaded into the address counter 22 (lower half) consisting of address registers 52 and 54. The data in the character buffer register 43, comprising 42 and 44, is loaded into the address counter (upper half) 56 and 58. Thus, a two-character LINK operation has established a new terminal memory address in the address counter 59 and 60 (52, 54, 56 and 58). To summarize, the LINK command character becomes the high order bits of the new address and the second character fetched becomes the lower order bits of the new address.

The LINK flip-flop 50 is reset upon clocking the two characters into the address registers 59 and 60, completing the link operation.

If the control character is an END OF LINE, an end of line flip-flop 62 is set. Subsequent fetches from the terminal memory 6 are disabled by disabling the REQUEST signal 38. This causes dummy reads from memory. Since there is no request, no memory data is gated to the input register 43. Memory output remains at its quiescent state which is all zero. At the time data is clocked into the input holding register 43, the null input character is converted to a blank by character generator 18. Thus, it seems to the logic that blanks are being read from the memory 6. The address register 60 is inhibited from decrementing addresses so that the data control does dummy reads repeatedly from the same address. When all 80 characters have been input, the address counter 60 rolls over to 80. This holds off further data input. When the next interrupt set signal 2 from the Timing and Control Circuitry 20 resets the 80 character counter 26, the END OF LINE flip-flop 62 is also reset thereby returning the logic to the normal character input mode.

The END OF PAGE operates identically to the END OF LINE except that the END OF PAGE flip-flop 24 is reset by a vertical sync flip-flop 64. Thus, after an END OF PAGE function is input from the terminal memory 6, blanks are delivered to the screen to the bottom of the screen. At the end of the screen display, the vertical sync signal 4 resets the END OF PAGE flip-flop 24 thereby returning the logic to its normal character mode.

Flags are functions disregarded by the REFRESH control apparatus. When a flag is fetched from the terminal memory 6 only the terminal address counter 60 is decremented and the REFRESH control goes on to fetch the next character from terminal memory 6.

Referring to FIG. 8, displayable characters are those with a zero in bit 7 (the most significant bit) of the character. These are transferred to the 80-character circulating memory 12 and 14 from the input holding register 43. At the same time, the 80-character counter 26 is decremented.

Display enhancements select the character set and the enhancement modes of, for example, inverse video, half-bright, underline and blinking. They have a zero in bit 6 and a 1 in bit 7 as shown in FIG. 8. The REFRESH control clocks inverse video into inverse video flip-flop 66 and sends this clocking signal on to a Display Option board 67. The Display Option board 67 clocks in the other 5 bits of a Control character. The output of the inverse video flip-flop 66 is entered into the 80-character shift registers 12 and 14 when the next character is entered. In the data stream, a Control character which changes the enhancements always precedes the data characters.

During the display of odd number lines on a visual display device, the REFRESH display circuitry is reading characters for the next even numbered row. There are 24 rows total. An even line, labeled as EVEN 8* in FIG. 6B, from the Timing and Control circuitry 20 indicates whether the display is on an even or odd line. This signal controls whether a rotating memory circulator clock signal shown as 0 CIRC K* and 0 CIRCEN L* in FIG. 6B from the Timing Control 20 is to be sent to the even or odd 80 character buffers 12 and 14. Thus during a display line on the screen, one set of the 80 character shift registers 12 and 14 is being loaded with new data from the terminal memory 6 while the other is being rapidly clocked. Characters for refreshing the screen are selected and clocked into an internal 8 bit register 16. The data is then sent to a ROM character generator 18.

Although preferred embodiments have been described for use with CRT displays, methods and apparatus incorporating the invention are useful in combination with many types of visual display apparatus including, but not limited to, for example, impact printers, thermal printers, laser beam raster scanned xerographic displays and the like.