SLET - cs

Huffman encoding

This method is named after D.A. Huffman, who developed the procedure in the 1950s. Figure 27-2 shows a histogram of the byte values from a large ASCII file. More than 96% of this file consists of only 31 characters: the lower case letters, the space, the comma, the period, and the carriage return. This observation can be used to make an appropriate compression scheme for this file. To start, we will assign each of these 31 common characters a five bit binary code: 00000 = "a", 00001 = "b", 00010 = "c", etc. This allows 96% of the file to be reduced in size by 5/8. The last of the five bit codes, 11111, will be a flag indicating that the character being transmitted is not one of the 31 common characters. The next eight bits in the file indicate what the character is, according to the standard ASCII assignment. This results in 4% of the characters in the input file requiring 5+8=13 bits. The idea is to assign frequently used characters fewer bits,

and seldom used characters more bits. In this example, the average number of bits required per original character is: 0.96×5 + 0.04×13 = 5.32. In other words, an overall compression ratio of: 8 bits/5.32 bits, or about 1.5:1.

Huffman encoding takes this idea to the extreme. Characters that occur most often, such the space and period, may be assigned as few as one or two bits. Infrequently used characters, such as: !, @, #, $ and %, may require a dozen or more bits. In mathematical terms, the optimal situation is reached when the number of bits used for each character is proportional to the logarithm of the character's probability of occurrence.

A clever feature of Huffman encoding is how the variable length codes can be packed together. Imagine receiving a serial data stream of ones and zeros. If each character is represented by eight bits, you can directly separate one character from the next by breaking off 8 bit chunks. Now consider a Huffman encoded data stream, where each character can have a variable number of bits. How do you separate one character from the next? The answer lies in the proper selection of the Huffman codes that enable the correct separation. An example will illustrate how this works.

Figure 27-3 shows a simplified Huffman encoding scheme. The characters A through G occur in the original data stream with the probabilities shown. Since the character A is the most common, we will represent it with a single bit, the code: 1. The next most common character, B, receives two bits, the code: 01. This continues to the least frequent character, G, being assigned six bits, 000011. As shown in this illustration, the variable length codes are resorted into eight bit groups, the standard for computer use.

When uncompression occurs, all the eight bit groups are placed end-to-end to form a long serial string of ones and zeros. Look closely at the encoding table of Fig. 27-3, and notice how each code consists of two parts: a number of zeros before a one, and an optional binary code after the one. This allows the binary data stream to be separated into codes without the need for delimiters or other marker between the codes. The uncompression program

looks at the stream of ones and zeros until a valid code is formed, and then starting over looking for the next character. The way that the codes are formed insures that no ambiguity exists in the separation.

A more sophisticated version of the Huffman approach is called arithmetic encoding. In this scheme, sequences of characters are represented by individual codes, according to their probability of occurrence. This has the advantage of better data compression, say 5-10%. Run-length encoding followed by either Huffman or arithmetic encoding is also a common strategy. As you might expect, these types of algorithms are very complicated, and usually left to data compression specialists.

To implement Huffman or arithmetic encoding, the compression and un-compression algorithms must agree on the binary codes used to represent each character (or groups of characters). This can be handled in one of two

ways. The simplest is to use a predefined encoding table that is always the same, regardless of the information being compressed. More complex schemes use encoding optimized for the particular data being used. This requires that the encoding table be included in the compressed file for use by the uncompression program. Both methods are common.

For SLET - III paper - UNIX and WINDOWS

X Window System

The X Window System (commonly X or X11) is a computer software system and network protocol that provides a graphical user interface (GUI) for networked computers, and was initially developed as part of Project Athena. It implements the X display protocol and provides windowing on raster graphics (bitmap) computer displays and manages keyboard and pointing device control functions. In its standard distribution, it is a complete, albeit simple, display and human interface solution, but also delivers a standard toolkit and protocol stack for building graphical user interfaces on most Unix-like operating systems and OpenVMS, and has been ported to many other contemporary general purpose operating systems. Desktop environments such as OpenWindows, CDE, GNOME, KDE, and Xfce, use the X Window System.
X provides the basic framework, or primitives, for building such GUI environments: drawing and moving windows on the screen and interacting with a mouse and/or keyboard. X does not mandate the user interface — individual client programs handle this. As such, the visual styling of X-based environments varies greatly; different programs may present radically different interfaces. X is built as an additional application layer on top of the operating system kernel.
Unlike previous display protocols, X was specifically designed to be used over network connections rather than on an integral or attached display device. X features network transparency: the machine where an application program (the client application) runs can differ from the user's local machine (the display server).
X originated at MIT in 1984. The current protocol version, X11, appeared in September 1987. The X.Org Foundation leads the X project, with the current reference implementation, X.Org Server, available as free and open source software under the MIT License and similar permissive licenses.^[1]

DesignFor more details on this topic, see X Window System protocols and architecture.

For more details on this topic, see X Window System core protocol.

Example deployment of X server: the X server receives input from a local keyboard and mouse and displays to a screen. A web browser and a terminal emulator run on the user's workstation and a software update application runs on a remote computer but is controlled and monitored from the user's machine.

X uses a client-server model: an X server communicates with various client programs. The server accepts requests for graphical output (windows) and sends back user input (from keyboard, mouse, or touchscreen). The server may function as:

an application displaying to a window of another display system
a system program controlling the video output of a PC
a dedicated piece of hardware.

This client-server terminology — the user's terminal being the server and the applications being the clients — often confuses new X users, because the terms appear reversed. But X takes the perspective of the application, rather than that of the end-user: X provides display and I/O services to applications, so it is a server; applications use these services, thus they are clients.
The communication protocol between server and client operates network-transparently: the client and server may run on the same machine or on different ones, possibly with different architectures and operating systems. A client and server can even communicate securely over the Internet by tunneling the connection over an encrypted network session.
An X client itself may emulate an X server by providing display services to other clients. This is known as "X nesting". Open-source clients such as Xnest and Xephyr support such X nesting.
To use an X client program on a remote machine, the user does the following:

On the local machine, open a terminal window
use telnet or ssh to connect to the remote machine
request local display/input service (e.g., export DISPLAY=[user's machine]:0 if not using SSH with X tunneling enabled)

The remote X client will then make a connection to the user's local X server, providing display and input to the user.
Alternatively, the local machine may run a small program that connects to the remote machine and starts the client application.
Practical examples of remote clients include:

administering a remote machine graphically
running a computationally intensive simulation on a remote Unix machine and displaying the results on a local Windows desktop machine
running graphical software on several machines at once, controlled by a single display, keyboard and mouse.

Principles

In 1984, Bob Scheifler and Jim Gettys set out the early principles of X:

Do not add new functionality unless an implementor cannot complete a real application without it.
It is as important to decide what a system is not as to decide what it is. Do not serve all the world's needs; rather, make the system extensible so that additional needs can be met in an upwardly compatible fashion.
The only thing worse than generalizing from one example is generalizing from no examples at all.
If a problem is not completely understood, it is probably best to provide no solution at all.
If you can get 90 percent of the desired effect for 10 percent of the work, use the simpler solution. (See also Worse is better.)
Isolate complexity as much as possible.
Provide mechanism rather than policy. In particular, place user interface policy in the clients' hands.

The first principle was modified during the design of X11 to: "Do not add new functionality unless you know of some real application that will require it."
X has largely kept to these principles. The sample implementation is developed with a view to extension and improvement of the implementation, while remaining compatible with the original 1987 protocol.

User interfaces

GNOME graphical user interface

KDE graphical user interface

Xfce graphical user interface

X is primarily a protocol and graphics primitives definition and it deliberately contains no specification for application user interface design, such as button, menu, or window title bar styles. Instead, application software – such as window managers, GUI widget toolkits and desktop environments, or application-specific graphical user interfaces - define and provide such details. As a result, there is no typical X interface and several desktop environments have been popular among users.
A window manager controls the placement and appearance of application windows. This may result in interfaces akin to those of Microsoft Windows or the Macintosh (examples include Metacity in GNOME, KWin in KDE, Xfwm in Xfce, or Compiz) or have radically different controls (such as a tiling window manager, like wmii or Ratpoison). Window managers range in sophistication and complexity from the bare-bones (e.g., twm, the basic window manager supplied with X, or evilwm, an extremely light window manager) to the more comprehensive desktop environments such as Enlightenment.
Many users use X with a desktop environment, which, aside from the window manager, include various applications using a consistent user interface. GNOME, KDE and Xfce are the most popular desktop environments. The Unix standard environment is the Common Desktop Environment (CDE). The freedesktop.org initiative addresses interoperability between desktops and the components needed for a competitive X desktop.
As X is responsible for keyboard and mouse interaction with graphical desktops, certain keyboard shortcuts have become associated with X. Control-Alt-Backspace typically terminates the currently running X session, while Control-Alt in conjunction with a function key switches to the associated virtual console. However, this is an implementation detail left to the design of an X server implementation and is not universal; for example, X server implementations for Windows and Macintosh typically do not provide these keyboard shortcuts.

Implementations

The X.Org implementation serves as the canonical implementation of X. Due to liberal licensing, a number of variations, both free and open source and proprietary, have appeared. Commercial UNIX vendors have tended to take the open source implementation and adapt it for their hardware, usually customizing it and adding proprietary extensions.

Cygwin/X running rootless on Microsoft Windows XP via the command (startx -- -rootless). The screen shows X applications (xeyes, xclock, xterm) sharing the screen with native Windows applications (Date and Time, Calculator).

Xming on Windows displaying Synaptic and nautilus

Up to 2004, XFree86 provided the most common X variant on free Unix-like systems. XFree86 started as a port of X for 386-compatible PCs and, by the end of the 1990s, had become the greatest source of technical innovation in X and the de facto standard of X development.^[2] Since 2004, however, the X.Org Server, a fork of XFree86, has become predominant.
While it is common to associate X with Unix, X servers also exist natively within other graphical environments. Hewlett-Packard's OpenVMS operating system includes a version of X with CDE, known as DECwindows, as its standard desktop environment. Apple's Mac OS X v10.3 (Panther) and Mac OS X v10.4 (Tiger) includes X11.app, based on XFree86 4.3 and X11R6.6, with better Mac OS X integration, on Mac OS X v10.5 (Leopard) Apple included X.org (X11R7.2 Codebase) instead of XFree86 (X11R6.8). Third-party servers under Mac OS 7, 8 and 9 included White Pine Software's eXodus and Apple's MacX.
Microsoft Windows is not shipped with support for X, but many third-party implementations exist, both free and open source software such as Cygwin/X, Xming (free up to 6.9.0.31) and WeirdX; and proprietary products such as Xmanager, Exceed, MKS X/Server, Reflection X, X-Win32, and Xming.
When an operating system with a native windowing system hosts X in addition, the X system can either use its own normal desktop in a separate host window or it can run rootless, meaning the X desktop is hidden and the host windowing environment manages the geometry and appearance of the hosted X windows within the host screen.

X terminals

A Network Computing Devices NCD-88k X terminal

An X terminal is a thin client that only runs an X server. This architecture became popular for building inexpensive terminal parks for many users to simultaneously use the same large computer server to execute application programs as clients of each user's X terminal. This use is very much aligned with the original intention of the MIT project.
X terminals explore the network (the local broadcast domain) using the X Display Manager Control Protocol to generate a list of available hosts that are allowed as clients. One of the client hosts should run an X display manager.
Dedicated (hardware) X terminals have become less common; a PC or modern thin client with an X server typically provides the same functionality at the same, or lower, cost.

limitations and criticisms of X

The UNIX-HATERS Handbook (1994) devoted an entire chapter to the problems of X.^[3] Why X Is Not Our Ideal Window System (1990) by Gajewska, Manasse and McCormack detailed problems in the protocol with recommendations for improvement.

User interface issues

The lack of design guidelines in X has resulted in several vastly different interfaces, and in applications that have not always worked well together. The ICCCM, a specification for client interoperability, has a reputation as being difficult to implement correctly. Further standards efforts such as Motif and CDE did not alleviate problems. This has frustrated users and programmers.^[4] Graphics programmers now generally address consistency of application look and feel and communication by coding to a specific desktop environment or to a specific widget toolkit, which also avoids having to deal directly with the ICCCM.

Computer accessibility related issues

Systems built upon the X windowing system may have accessibility issues that make utilization of a computer difficult for accessibility users, including right click, double click, middle click, mouseover, and focus stealing.

Lack of audio support

The X protocol provides no facilities for handling audio, leaving it to the operating system or its audio subsystems like OSS or ALSA to provide support for audio hardware and sound playback. Most programmers simply use local, OS-specific sound APIs. The first generation of client-server sound systems included rplay and Network Audio System. More recent efforts have produced EsounD (older GNOME), aRts (older KDE), and PulseAudio to name a few. In 2001, the X.org foundation announced the development of the Media Application Server (MAS) to remedy this problem. However, none of these are generally used as a solution to the problem. Another effort, X11 AUDIO, was announced by Helge Bahmann in September 2007^[5] as an extension to the X server. However, it is not still clear why audio management (like printer management) should be a part of the display server. Non X-based operating systems (like Microsoft Windows or Mac OS X) handle display and audio separately with no evident problems, as do the various GNU/Linux distributions like Ubuntu or Fedora. With the development of the gstreamer multimedia framework, this limitation has been rendered moot, thus it is unlikely that audio support will be built into X.

Network

Example of tunnelling an X11 application over SSH.

An X client cannot generally be detached from one server and reattached to another, as with Virtual Network Computing (VNC), though certain specific applications and toolkits are able to provide this facility.^[6] Workarounds (VNC :0 viewers) also exist to make the current X-server screen available via VNC.
Network traffic between an X server and remote X clients is not encrypted by default. An attacker with a packet sniffer can intercept it, making it possible to view anything displayed to or sent from the user's screen. The most common way to encrypt X traffic is to establish a Secure Shell (SSH) tunnel for communication. Lack of security is actually a feature of X, because it removes an extremely complex and high vulnerability target (secure connection manipulation) from the large and complicated display server. Vulnerabilities in SSH can (and should) be patched independently and quickly, without affecting the (large) display server, whose code is unaffected.

Client-server separation

X's design requires the clients and server to operate separately, and device independence and the separation of client and server incur overhead. Most of the overhead comes from network round-trip delay time between client and server (latency) rather than from the protocol itself: the best solutions to performance issues depend on efficient application design.^[7] A common criticism of X is that its network features result in excessive complexity and decreased performance if only used locally. That used to be the case, but modern X implementations use unix domain sockets for connections on the same host. Additionally shared memory (via the MIT-SHM extension) can be employed for faster client-server communication.^[8] However, the programmer must still explicitly activate and use the shared memory extension and must also provide fallback paths in order to stay compatible with older implementations.

Competitors to X

For graphics, Unix-like systems use X almost universally. However, some people have attempted writing alternatives to and replacements for X. Historical alternatives include Sun's NeWS, which failed in the market, and NeXT's Display PostScript, which was discarded in favor of Apple's entirely new Quartz in Mac OS X.
Mike Paquette, one of the authors of Quartz, explained why Apple did not move from Display PostScript to X, and chose instead to develop its own window server, by saying that once Apple added support for all the features it wanted to include into X11, it would not bear much resemblance to X11 nor be compatible with other servers anyway.^[9]
Other attempts to address criticisms of X by replacing it completely include Berlin/Fresco and the Y Window System. These alternatives have seen negligible take-up, however, and commentators widely doubt the viability of any replacement that does not preserve backward compatibility with X.
Other competitors attempt to avoid the overhead of X by working directly with the hardware. Such projects include DirectFB. The Direct Rendering Infrastructure (DRI), which aims to provide a reliable kernel-level interface to the framebuffer, may make these efforts redundant. However, in Linux embedded systems requiring real-time capabilities (e.g. using RTAI), the use of hardware acceleration via DRI is discouraged^{[citation needed]}; X may be unsuitable for such applications^{[citation needed]}.
Other ways to achieve network transparency for graphical services include:

the SVG Terminal, a protocol to update Scalable Vector Graphics (SVG) content in a browser in near-real-time
Virtual Network Computing (VNC), a very low-level system which sends compressed bitmaps across the network; the Unix implementation includes an X server
Citrix XenApp, an X-like product for Microsoft Windows
Tarantella, which provides a Java client for use in web browsers
RAWT, IBM's Java-only Remote AWT, which implements a Java "server" and simple hooks for any remote Java client (see also: Setting up RAWT)

DSPSOFT INC offers a partially proprietary windowing system called MicroXwin that is initially targeted at embedded systems.^{[citation needed]} The system is not a full-fledged replacement for X but maintains binary compatibility with standard X clients while providing better performance and significantly lower memory overhead by a different architecture of design that directly implements the system as a kernel module.^[10] The kernel module is proprietary while the user space libraries, libX11 (counterpart of Xlib) and libXext, are available under BSD style license.

Sasikala Subramani

Monday, October 31, 2011

Sunday, June 12, 2011

SLET computer science

SLET questions for computer science