Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, error detection and correction, data transmission and data storage. Codes are studied by various scientific disciplines—such as information theory, electrical engineering, mathematics and computer science—for the purpose of designing efficient and reliable data transmission methods; this involves the removal of redundancy and the correction or detection of errors in the transmitted data. There are four types of coding: Data compression Error control Cryptographic coding Line codingData compression attempts to remove redundancy from the data from a source in order to transmit it more efficiently. For example, Zip data compression makes data files smaller, for purposes such as to reduce Internet traffic. Data compression and error correction may be studied in combination. Error correction adds extra data bits to make the transmission of data more robust to disturbances present on the transmission channel.
The ordinary user may not be aware of many applications using error correction. A typical music CD uses the Reed-Solomon code to correct for scratches and dust. In this application the transmission channel is the CD itself. Cell phones use coding techniques to correct for the fading and noise of high frequency radio transmission. Data modems, telephone transmissions, the NASA Deep Space Network all employ channel coding techniques to get the bits through, for example the turbo code and LDPC codes. In 1948, Claude Shannon published "A Mathematical Theory of Communication", an article in two parts in the July and October issues of the Bell System Technical Journal; this work focuses on the problem of. In this fundamental work he used tools in probability theory, developed by Norbert Wiener, which were in their nascent stages of being applied to communication theory at that time. Shannon developed information entropy as a measure for the uncertainty in a message while inventing the field of information theory.
The binary Golay code was developed in 1949. It is an error-correcting code capable of correcting up to three errors in each 24-bit word, detecting a fourth. Richard Hamming won the Turing Award in 1968 for his work at Bell Labs in numerical methods, automatic coding systems, error-detecting and error-correcting codes, he invented the concepts known as Hamming codes, Hamming windows, Hamming numbers, Hamming distance. The aim of source coding is to make it smaller. Data can be seen as a random variable X: Ω → X, where x ∈ X appears with probability P. Data are encoded by strings over an alphabet Σ. A code is a function C: X → Σ ∗. C is the code word associated with x. Length of the code word is written as l. Expected length of a code is l = ∑ x ∈ X l P The concatenation of code words C = C C... C; the code word of the empty string is the empty string itself: C = ϵ C: X → Σ ∗ is non-singular if injective. C: X ∗ → Σ ∗ is uniquely decodable if injective. C: X → Σ ∗ is instantaneous if C is not a prefix of C.
Entropy of a source is the measure of information. Source codes try to reduce the redundancy present in the source, represent the source with fewer bits that carry more information. Data compression which explicitly tries to minimize the average length of messages according to a particular assumed probability model is called entropy encoding. Various techniques used by source coding schemes try to achieve the limit of Entropy of the source. C ≥ H, where H is entropy of source, C is the bitrate after compression
Data storage is the recording of information in a storage medium. DNA and RNA, phonographic recording, magnetic tape, optical discs are all examples of storage media. Recording is accomplished by any form of energy. Electronic data storage requires electrical power to retrieve data. Data storage in a digital, machine-readable medium is sometimes called digital data. Computer data storage is one of the core functions of a general purpose computer. Electronic documents can be stored in much less space than paper documents. Barcodes and magnetic ink character recognition are two ways of recording machine-readable data on paper. A recording medium is a physical material. Newly created information is distributed and can be stored in four storage media–print, film and optical–and seen or heard in four information flows–telephone, radio and TV, the Internet as well as being observed directly. Digital information is stored on electronic media in many different recording formats. With electronic media, the data and the recording media are sometimes referred to as "software" despite the more common use of the word to describe computer software.
With static media, art materials such as crayons may be considered both equipment and medium as the wax, charcoal or chalk material from the equipment becomes part of the surface of the medium. Some recording media may be temporary either by nature. Volatile organic compounds may be used to preserve the environment or to purposely make data expire over time. Data such as smoke signals or skywriting are temporary by nature. Depending on the volatility, a gas or a liquid surface such as a lake would be considered a temporary recording medium if at all. A 2003 UC Berkeley report estimated that about five exabytes of new information were produced in 2002, that 92% of this data was stored on hard disk drives; this was about twice the data produced in 2000. The amount of data transmitted over telecommunication systems in 2002 was nearly 18 exabytes—three and a half times more than was recorded on non-volatile storage. Telephone calls constituted 98% of the telecommunicated information in 2002; the researchers' highest estimate for the growth rate of newly stored information was more than 30% per year.
It has been estimated that the year 2002 was the beginning of the digital age for information storage: an age in which more information is stored on digital storage devices than on analog storage devices. In 1986 1% of the world's capacity to store information was in digital format; these figures correspond to less than three compressed exabytes in 1986, 295 compressed exabytes in 2007. The quantity of digital storage doubled every three years. In a more limited study, the International Data Corporation estimated that the total amount of digital data in 2007 was 281 exabytes, that the total amount of digital data produced exceeded the global storage capacity for the first time. A study published in 2011 estimated that the world's technological capacity to store information in analog and digital devices grew from less than three exabytes in 1986, to 295 exabytes in 2007, doubles every three years. Data storage portal Bennett, John C.. "'JISC/NPO Studies on the Preservation of Electronic Materials: A Framework of Data Types and Formats, Issues Affecting the Long Term Preservation of Digital Material".
British Library Research and Innovation Report 50. History of Computer Storage from 1928 to 2013 History of Computer Data Storage History of Storage from Cave Paintings to Electrons The Evolution of Data Storage
A space–time code is a method employed to improve the reliability of data transmission in wireless communication systems using multiple transmit antennas. STCs rely on transmitting multiple, redundant copies of a data stream to the receiver in the hope that at least some of them may survive the physical path between transmission and reception in a good enough state to allow reliable decoding. Space time codes may be split into two main types: Space–time trellis codes distribute a trellis code over multiple antennas and multiple time-slots and provide both coding gain and diversity gain. Space–time block codes act on a block of data at once and provide diversity gain but doesn't provide coding gain. STC may be further subdivided according to. In coherent STC, the receiver knows the channel impairments through training or some other form of estimation; these codes have been studied more and division algebras over number fields have now become the standard tool for constructing such codes. In noncoherent STC the receiver does not know the channel impairments but knows the statistics of the channel.
In differential space–time codes neither the channel nor the statistics of the channel are available. Diversity scheme – the concept from which STC arose. MIMO – the term for wireless communication systems employing multiple antennas at both a transmitter and a receiver. Louay M. A. Jalloul and Sam. P. Alex, "Evaluation Methodology and Performance of an IEEE 802.16e System", Presented to the IEEE Communications and Signal Processing Society, Orange County Joint Chapter, December 7, 2006. Available at: http://chapters.comsoc.org/comsig/meet.html Sam P. Alex and Louay M. A. Jalloul, "Performance Evaluation of MIMO in IEEE802.16e/WiMAX", IEEE Journal of Selected Topics in Signal Processing, VOL. 2, NO. 2, April, 2008
A letter is a grapheme in an alphabetic system of writing. It is a visual representation of the smallest unit of spoken sound. Letters broadly correspond to phonemes in the spoken form of the language, although there is a consistent, exact correspondence between letters and phonemes. Written signs in other writing systems are called logograms; the contemporary English-language alphabet, known as Roman style, consists of twenty-six letters. Each letter corresponds to one or more sounds, the letters are combined in the order of sounds to make words. A letter is classed depending on how its sound is produced; the basic Roman alphabet is used with slight variations. Some versions contain as few as some as many as thirty. Letters have specific names associated with them, which may differ with language and history. Z, for example, is called zed in all English-speaking countries except the US, where it is named zee; as elements of alphabets, letters have prescribed orders. In Spanish, for instance, ñ is a separate letter, sorted after n.
In English, n and ñ are classified alike. As symbols that indicate segmental speech, letters are associated with phonetics. In a purely phonemic alphabet, a single phoneme is denoted by a single letter, although in history and in practice letters indicate more than one phoneme. There are more phonemes, in English -- about 44 -- than there are letters of the alphabet. A letter may therefore be associated with more than one phoneme, with the phoneme determined by the surrounding letters or etymology of the word. Regional accents have a significant effect; as an example of positional effects, the letter c is pronounced before a, o, u, or consonants, but is pronounced before e, i, or y. Conversely, the same phoneme may be shared by more than one letter, as shown by the c and s in fence and tense. A pair of letters designating a single phoneme is called a digraph. Examples of digraphs in English include ch, sh, th. A phoneme can be represented by three letters, called a trigraph. An example is the combination sch in German.
Letters may have a numerical or quantitative value. This applies to the letters of other writing systems. In English, Arabic numerals are used instead of letters. Greek and Roman letters are used as mathematical symbols in expressions. People and objects are sometimes named after letters, for one of these reasons: The letter is an abbreviation, e.g. "G-man" as slang for a Federal Bureau of Investigation agent, arose as short for "Government Man" Alphabetical order used as a counting system, e.g. Plan A, Plan B, etc.. The shape of the letter, e.g. A-clamp, D-ring, F-clamp, G-clamp, H-block, H engine, O-ring, R-clip, U engine, V engine, Z-drive, a river delta, omega block Other reasons, e.g. X-ray after "x the unknown" in algebra, because the discoverer did not know what they were The Consistori del Gay Saber was the first literary academy in the world and held the Floral Games to award the best troubadour with the violeta d'aur top prize. Guilhem Molinier, a member of the academy, gave a definition of the letter in his Leys d'Amors, a book aimed at regulating then-flourishing Occitan poetry: Before there were alphabets, there were pictographs, or symbols.
Ancient Egyptian examples date to about 3500 BCE. Pictographs could communicate basic ideas, but were general and ambiguous if they were comprehensible at all. Tense, for example, could not be specified, symbols do not carry meaning across cultures. Memorization of tens of thousands of symbols is a daunting task; the relative ease of memorizing 26 letters contributed to the spread of literacy throughout the world. The first consonantal alphabet found emerged around 1800 BCE to represent the language of the Phoenicians, Semitic workers in Egypt, was derived from the alphabetic principles of the Egyptian hieroglyphs. Our present Roman system derives from this Phoenician alphabet. Nineteen of our present letters evolved from the early Phoenician forms; the Greek alphabet, adapted around 800 BCE, added four letters. This was the first alphabet assigning letters not only to consonant sounds, but to vowels; the Roman Empire brought the development and refinement of our Roman alphabet, beginning around 500 BCE.
The Romans dropped certain letters to accommodate Greek and Etruscan words. By about the fifth century CE, the beginnings of lowercase letterforms began to emerge in Roman writing, but they did not come into common use until the end of the Middle Ages, a thousand years later. Letter, borrowed from Old French letre, entered Middle English around 1200 CE displacing the native English term bōcstaf. Letter is descended from the Latin littera, which may have descended from the Greek "διφθέρα", via Etruscan. More the development of SMS technology is eliminating use of unnecessary letters in informal communication. Time pressure and limited character counts have introduced common abbreviations and variations such as gr8fl
In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems. Algorithms can perform calculation, data processing, automated reasoning, other tasks; as an effective method, an algorithm can be expressed within a finite amount of space and time and in a well-defined formal language for calculating a function. Starting from an initial state and initial input, the instructions describe a computation that, when executed, proceeds through a finite number of well-defined successive states producing "output" and terminating at a final ending state; the transition from one state to the next is not deterministic. The concept of algorithm has existed for centuries. Greek mathematicians used algorithms in the sieve of Eratosthenes for finding prime numbers, the Euclidean algorithm for finding the greatest common divisor of two numbers; the word algorithm itself is derived from the 9th century mathematician Muḥammad ibn Mūsā al-Khwārizmī, Latinized Algoritmi.
A partial formalization of what would become the modern concept of algorithm began with attempts to solve the Entscheidungsproblem posed by David Hilbert in 1928. Formalizations were framed as attempts to define "effective calculability" or "effective method"; those formalizations included the Gödel–Herbrand–Kleene recursive functions of 1930, 1934 and 1935, Alonzo Church's lambda calculus of 1936, Emil Post's Formulation 1 of 1936, Alan Turing's Turing machines of 1936–37 and 1939. The word'algorithm' has its roots in Latinizing the name of Muhammad ibn Musa al-Khwarizmi in a first step to algorismus. Al-Khwārizmī was a Persian mathematician, astronomer and scholar in the House of Wisdom in Baghdad, whose name means'the native of Khwarazm', a region, part of Greater Iran and is now in Uzbekistan. About 825, al-Khwarizmi wrote an Arabic language treatise on the Hindu–Arabic numeral system, translated into Latin during the 12th century under the title Algoritmi de numero Indorum; this title means "Algoritmi on the numbers of the Indians", where "Algoritmi" was the translator's Latinization of Al-Khwarizmi's name.
Al-Khwarizmi was the most read mathematician in Europe in the late Middle Ages through another of his books, the Algebra. In late medieval Latin, English'algorism', the corruption of his name meant the "decimal number system". In the 15th century, under the influence of the Greek word ἀριθμός'number', the Latin word was altered to algorithmus, the corresponding English term'algorithm' is first attested in the 17th century. In English, it was first used in about 1230 and by Chaucer in 1391. English adopted the French term, but it wasn't until the late 19th century that "algorithm" took on the meaning that it has in modern English. Another early use of the word is from 1240, in a manual titled Carmen de Algorismo composed by Alexandre de Villedieu, it begins thus: Haec algorismus ars praesens dicitur, in qua / Talibus Indorum fruimur bis quinque figuris. Which translates as: Algorism is the art by which at present we use those Indian figures, which number two times five; the poem is a few hundred lines long and summarizes the art of calculating with the new style of Indian dice, or Talibus Indorum, or Hindu numerals.
An informal definition could be "a set of rules that defines a sequence of operations". Which would include all computer programs, including programs that do not perform numeric calculations. A program is only an algorithm if it stops eventually. A prototypical example of an algorithm is the Euclidean algorithm to determine the maximum common divisor of two integers. Boolos, Jeffrey & 1974, 1999 offer an informal meaning of the word in the following quotation: No human being can write fast enough, or long enough, or small enough† to list all members of an enumerably infinite set by writing out their names, one after another, in some notation, but humans can do something useful, in the case of certain enumerably infinite sets: They can give explicit instructions for determining the nth member of the set, for arbitrary finite n. Such instructions are to be given quite explicitly, in a form in which they could be followed by a computing machine, or by a human, capable of carrying out only elementary operations on symbols.
An "enumerably infinite set" is one whose elements can be put into one-to-one correspondence with the integers. Thus and Jeffrey are saying that an algorithm implies instructions for a process that "creates" output integers from an arbitrary "input" integer or integers that, in theory, can be arbitrarily large, thus an algorithm can be an algebraic equation such as y = m + n – two arbitrary "input variables" m and n that produce an output y. But various authors' attempts to define the notion indicate that the word implies much more than this, something on the order of: Precise instructions for a fast, efficient, "good" process that specifies the "moves" of "the computer" to find and process arbitrary input integers/symbols m and n, symbols + and =... and "effectively" produce, in a "reasonable" time, output-integer y at a specified place and in a specified format
In linguistics, a word is the smallest element that can be uttered in isolation with objective or practical meaning. This contrasts with a morpheme, the smallest unit of meaning but will not stand on its own. A word may consist of a single morpheme, or several, whereas a morpheme may not be able to stand on its own as a word. A complex word will include a root and one or more affixes, or more than one root in a compound. Words can be put together to build larger elements of language, such as phrases and sentences; the term word may refer to a spoken word or to a written word, or sometimes to the abstract concept behind either. Spoken words are made up of units of sound called phonemes, written words of symbols called graphemes, such as the letters of the English alphabet; the difficulty of deciphering a word depends on the language. Dictionaries categorize a language's lexicon into lemmas; these can be taken as an indication of what constitutes a "word" in the opinion of the writers of that language.
The most appropriate means of measuring the length of a word is by counting its syllables or morphemes. When a word has multiple definitions or multiple senses, it may result in confusion in a debate or discussion. Leonard Bloomfield introduced the concept of "Minimal Free Forms" in 1926. Words are thought of as the smallest meaningful unit of speech; this correlates phonemes to lexemes. However, some written words are not minimal free forms; some semanticists have put forward a theory of so-called semantic primitives or semantic primes, indefinable words representing fundamental concepts that are intuitively meaningful. According to this theory, semantic primes serve as the basis for describing the meaning, without circularity, of other words and their associated conceptual denotations. In the Minimalist school of theoretical syntax, words are construed as "bundles" of linguistic features that are united into a structure with form and meaning. For example, the word "koalas" has semantic features, category features, number features, phonological features, etc.
The task of defining what constitutes a "word" involves determining where one word ends and another word begins—in other words, identifying word boundaries. There are several ways to determine where the word boundaries of spoken language should be placed: Potential pause: A speaker is told to repeat a given sentence allowing for pauses; the speaker will tend to insert pauses at the word boundaries. However, this method is not foolproof: the speaker could break up polysyllabic words, or fail to separate two or more linked words. Indivisibility: A speaker is told to say a sentence out loud, is told to say the sentence again with extra words added to it. Thus, I have lived in this village for ten years might become My family and I have lived in this little village for about ten or so years; these extra words will tend to be added in the word boundaries of the original sentence. However, some languages have infixes; some have separable affixes. Phonetic boundaries: Some languages have particular rules of pronunciation that make it easy to spot where a word boundary should be.
For example, in a language that stresses the last syllable of a word, a word boundary is to fall after each stressed syllable. Another example can be seen in a language that has vowel harmony: the vowels within a given word share the same quality, so a word boundary is to occur whenever the vowel quality changes. Not all languages have such convenient phonetic rules, those that do present the occasional exceptions. Orthographic boundaries: See below. In languages with a literary tradition, there is interrelation between orthography and the question of what is considered a single word. Word separators are common in modern orthography of languages using alphabetic scripts, but these are a modern development. In English orthography, compound expressions may contain spaces. For example, ice cream, air raid shelter and get up each are considered to consist of more than one word. Not all languages delimit words expressly. Mandarin Chinese is a analytic language, making it unnecessary to delimit words orthographically.
However, there are many multiple-morpheme compounds in Mandarin, as well as a variety of bound morphemes that make it difficult to determine what constitutes a word. Sometimes, languages which are close grammatically will consider the same order of words in different ways. For example, reflexive verbs in the French infinitive are separate from their respective particle, e.g. se laver, whereas in Portuguese they are hyphenated, e.g. lavar-se, in Spanish they are joined, e.g. lavarse. Japanese uses orthographic cues to delim
Telegraphy is the long-distance transmission of textual or symbolic messages without the physical exchange of an object bearing the message. Thus semaphore is a method of telegraphy. Telegraphy requires that the method used for encoding the message be known to both sender and receiver. Many methods are designed according to the limits of the signalling medium used; the use of smoke signals, reflected light signals, flag semaphore signals are early examples. In the 19th century, the harnessing of electricity led to the invention of electrical telegraphy; the advent of radio in the early 20th century brought about radiotelegraphy and other forms of wireless telegraphy. In the Internet age, telegraphic means developed in sophistication and ease of use, with natural language interfaces that hide the underlying code, allowing such technologies as electronic mail and instant messaging; the word "telegraph" was first coined by the French inventor of the Semaphore telegraph, Claude Chappe, who coined the word "semaphore".
A "telegraph" is a device for transmitting and receiving messages over long distances, i.e. for telegraphy. The word "telegraph" alone now refers to an electrical telegraph. Wireless telegraphy, transmission of messages over radio with telegraphic codes. Contrary to the extensive definition used by Chappe, Morse argued that the term telegraph can be applied only to systems that transmit and record messages at a distance; this is to be distinguished from semaphore, which transmits messages. Smoke signals, for instance, are to be considered semaphore, not telegraph. According to Morse, telegraph dates only from 1832 when Pavel Schilling invented one of the earliest electrical telegraphs. A telegraph message sent by an electrical telegraph operator or telegrapher using Morse code was known as a telegram. A cablegram was a message sent by a submarine telegraph cable shortened to a cable or a wire. A Telex was a message sent by a Telex network, a switched network of teleprinters similar to a telephone network.
A wire picture or wire photo was a newspaper picture, sent from a remote location by a facsimile telegraph. A diplomatic telegram known as a diplomatic cable, is the term given to a confidential communication between a diplomatic mission and the foreign ministry of its parent country; these continue to be called cables regardless of the method used for transmission. Passing messages by signalling over distance is an ancient practice. One of the oldest examples is the signal towers of the Great Wall of China. In 400 BC, signals could drum beats. By 200 BC complex flag signalling had developed, by the Han dynasty signallers had a choice of lights, flags, or gunshots to send signals. By the Tang dynasty a message could be sent 700 miles in 24 hours; the Ming dynasty added artillery to the possible signals. While the signalling was complex, only predetermined messages could be sent; the Chinese signalling system extended well beyond the Great Wall. Signal towers away from the wall were used to give early warning of an attack.
Others were built further out as part of the protection of trade routes the Silk Road. Signal fires were used in Europe and elsewhere for military purposes; the Roman army made frequent use of them, as did their enemies, the remains of some of the stations still exist. Few details have been recorded of European/Mediterranean signalling systems and the possible messages. One of the few for which details are known is a system invented by Aeneas Tacticus. Tacitus's system had water filled pots at the two signal stations which were drained in synchronisation. Annotation on a floating scale indicated which message was being received. Signals sent by means of torches indicated when to start and stop draining to keep the synchronisation. None of the signalling systems discussed above are true telegraphs in the sense of a system that can transmit arbitrary messages over arbitrary distances. Lines of signalling relay stations can send messages to any required distance, but all these systems are limited to one extent or another in the range of messages that they can send.
A system like flag semaphore, with an alphabetic code, can send any given message, but the system is designed for short-range communication between two persons. An engine order telegraph, used to send instructions from the bridge of a ship to the engine room, fails to meet both criteria. There was only one ancient signalling system described; that was a system using the Polybius square to encode an alphabet. Polybius suggested using two successive groups of torches to identify the coordinates of the letter of the alphabet being transmitted; the number of said torches held up signalled the grid square. The system would have been slow for military purposes and there is no record of it being used. An optical telegraph, or semaphore telegraph is a telegraph consisting of a line of stations in towers or natural high points which signal to each other by means of shutters or paddles. Early proposals for an optical telegraph system were made to the Royal Society by Robert Hooke in 1684 and were first implemented on an experimental level by Sir Richard Lovell Edgeworth in 1767.
The first successful optical telegraph network was invented by Claude Chappe and operated in France from 1