Meta tags:

Headings (most frequently used words):

codes, variable, length, encoding, contents, general, structure, and, their, extensions, see, also, notes, references, further, reading, non, singular, uniquely, decodable, prefix,

Text of the page (most frequently used words):
the (66), and (37), code (32), texttt (29), this (23), codes (22), for (21), source (21), #length (17), #coding (17), displaystyle (17), variable (14), encoding (14), bit (14), non (13), prefix (13), edit (13), which (13), symbol (13), are (13), with (12), from (12), example (12), can (12), mapsto (12), compression (11), symbols (11), mapping (10), string (10), singular (10), frac (9), sequence (9), data (8), huffman (8), unit (8), byte (8), characters (8), not (8), uniquely (8), decodable (8), wikipedia (7), its (7), utf (7), units (7), character (7), set (7), possible (7), such (7), extension (7), 011 (7), that (6), each (6), page (5), entropy (5), theory (5), lz77 (5), bits (5), used (5), target (5), article (5), two (5), when (5), finite (5), general (5), contents (4), search (4), text (4), may (4), references (4), rate (4), information (4), compressed (4), dpcm (4), video (4), methods (4), shannon (4), other (4), lossless (4), times (4), number (4), would (4), codeword (4), encodings (4), their (4), main (4), codewords (4), but (4), useful (4), existing (4), more (4), hide (4), move (4), sidebar (4), toggle (3), view (3), additional (3), terms (3), using (3), use (3), all (3), articles (3), december (3), 2009 (3), different (3), quantization (3), dwt (3), daubechies (3), wavelet (3), transform (3), dct (3), frame (3), concepts (3), rle (3), image (3), range (3), lossy (3), context (3), golomb (3), adaptive (3), systems (3), applications (3), reading (3), compatibility (3), single (3), see (3), also (3), per (3), because (3), after (3), same (3), free (3), encoded (3), however (3), restrictions (3), 10011 (3), 01110 (3), 1110 (3), map (3), any (3), create (3), will (3), always (3), some (3), these (3), extensions (3), singletons (3), lead (3), trail (3), encode (3), bytes (3), sources (3), read (3), tools (3), languages (2), table (2), contact (2), about (2), privacy (2), policy (2), available (2), under (2), was (2), rendered (2), categories (2), needing (2), short (2), description (2), wikidata (2), index (2), david (2), community (2), grammar (2), structures (2), motion (2), vector (2), estimation (2), compensation (2), parts (2), codec (2), quality (2), types (2), display (2), resolution (2), vbr (2), cbr (2), abr (2), spiht (2), deflate (2), psychoacoustic (2), mdct (2), wlpc (2), lsp (2), lar (2), celp (2), acelp (2), lpc (2), fft (2), adpcm (2), law (2), audio (2), type (2), bwt (2), mtf (2), lzss (2), ans (2), pair (2), lempel (2), ziv (2), fano (2), arithmetic (2), berstel (2), encyclopedia (2), cambridge (2), 978 (2), isbn (2), pages (2), errata (2), further (2), most (2), common (2), intended (2), ascii (2), does (2), notes (2), instruction (2), error (2), zero (2), were (2), expected (2), above (2), decoding (2), aabacdab (2), 110 (2), 111 (2), whether (2), shown (2), concept (2), special (2), thus (2), given (2), known (2), formal (2), acceptable (2), original (2), message (2), mapped (2), valid (2), follow (2), longer (2), generate (2), transmission (2), than (2), still (2), equivalent (2), strings (2), order (2), sequences (2), total (2), into (2), maps (2), contrast (2), values (2), well (2), like (2), only (2), multibyte (2), software (2), while (2), come (2), multiunit (2), though (2), structure (2), assigned (2), one (2), 256 (2), allow (2), english (2), computer (2), arbitrarily (2), learn (2), help (2), citations (2), appearance (2), upload (2), file (2), changes (2), links (2), history (2), log (2), account (2), donate (2), menu (2), add, topic, mobile, cookie, statement, statistics, developers, conduct, legal, safety, contacts, disclaimers, apply, site, you, agree, registered, trademark, profit, organization, wikimedia, foundation, inc, creative, commons, attribution, sharealike, license, parsoid, last, edited, july, 2026, utc, hidden, dmy, dates, 2021, retrieved, https, org, php, title, length_encoding, oldid, 1365342874, phil, katz, mark, adler, people, hutter, prize, smallest, problem, symmetry, redundancy, distortion, kolmogorov, complexity, timeline, suffix, array, lapped, deblocking, filter, characteristics, interlace, ezw, klt, fractal, chain, texture, standard, test, psnr, pixel, macroblock, artifact, color, space, tree, chroma, subsampling, model, sub, band, speech, sound, silence, sampling, nyquist, theorem, latency, dynamic, convolution, companding, predictive, dst, discrete, cosine, bzip2, lzham, lzma, lha, lzh, brotli, zstandard, lzfse, lzs, lzx, hybrid, ppm, paq, ldct, sequitur, dmc, incremental, delta, ctw, snappy, lzwl, lzw, lzrw, lzo, lzjb, lz4, 842, dictionary, levenshtein, gamma, fibonacci, exp, universal, unary, tunstall, elias, modified, canonical, asymmetric, numeral, draft, online, jean, perrin, dominique, reutenauer, christophe, 2010, mathematics, vol, 129, 1187, 94001, zbl, 521, 88831, university, press, automata, xii, 191, salomon, september, 2007, 84628, 958, springer, verlag, based, found, crispin, 2005, 17487, rfc4042, doi, ietf, efficient, transformation, formats, unicode, real, life, represents, exactly, manner, just, described, uses, pairs, less, never, gained, traction, interchange, due, incompatibility, ubiquitous, role, instead, being, taken, preserve, sbcs, dbcs, double, tbcs, triple, lmbcs, lotus, multi, wide, wchar_t, computing, architecture, kruskal, count, compresses, much, recovered, probabilities, represent, textstyle, left, right, 00100110111010, know, encodes, below, means, decoded, instantaneously, entire, received, commonly, names, case, vlq, quantity, leb128, block, instantaneous, consider, again, previous, section, since, interpreted, decodings, completely, there, syntax, determine, elements, permit, checking, those, babe, cdb, 011101110011, demonstrated, looking, bitstring, terminated, soon, cannot, unambiguously, starts, new, decided, sardinas, patterson, algorithm, feature, required, necessary, compact, many, larger, way, detect, recover, errors, security, protect, undetectable, tampering, both, loss, where, becomes, empty, injective, strictly, nested, decreasing, generality, turn, obtained, concatenating, corresponding, produced, precise, mathematical, definition, follows, let, sets, called, respectively, function, over, naturally, referred, homomorphism, alphabets, language, clearly, distinguishes, leads, trails, overlapping, value, ranges, older, often, reuse, making, harder, parse, correctly, cause, false, positives, searches, make, corrupted, disrupt, long, designed, searching, works, reliably, corruption, affects, containing, bad, four, six, heart, represented, combination, hexadecimal, system, minimises, disruption, keeping, others, require, multiple, creates, three, consist, first, afterwards, input, must, handle, unlikely, likely, shorter, giving, low, examples, strategies, usually, result, need, increase, without, breaking, constraint, obvious, choice, 536, change, break, therefore, might, feasible, backward, reasons, they, sometimes, pack, fewer, early, increases, memory, purpose, have, obsolete, algorithms, disks, microcomputers, adventure, games, decompressed, back, almost, close, fixed, large, blocks, beyond, logarithm, possibilities, comes, perhaps, small, probability, failure, independent, identically, distributed, scheme, differing, lengths, representation, through, communication, channel, storage, medium, science, how, remove, please, unsourced, material, challenged, jstor, scholar, books, newspapers, news, find, removed, adding, reliable, improve, needs, redirected, item, projects, printable, version, download, pdf, print, export, switch, legacy, parser, get, shortened, url, cite, permanent, link, related, what, here, actions, talk, 한국어, 日本語, français, català, subsection, top, personal, recent, portal, contribute, random, current, events, navigation, jump, content,

Text of the page (random words):
variable length encoding wikipedia jump to content main menu main menu move to sidebar hide navigation main page contents current events random article about wikipedia contact us contribute help learn to edit community portal recent changes upload file special pages search search appearance donate create account log in personal tools donate create account log in contents move to sidebar hide top 1 general structure 2 codes and their extensions toggle codes and their extensions subsection 2 1 non singular codes 2 2 uniquely decodable codes 2 3 prefix codes 3 see also 4 notes 5 references 6 further reading toggle the table of contents variable length encoding 5 languages català français 日本語 한국어 中文 edit links article talk english read edit view history tools tools move to sidebar hide actions read edit view history general what links here related changes upload file permanent link page information cite this page get shortened url switch to legacy parser print export download as pdf printable version in other projects wikidata item appearance move to sidebar hide from wikipedia the free encyclopedia redirected from variable length code encoding which maps information to a variable number of bits this article needs more citations please help improve this article by adding citations to reliable sources unsourced material may be challenged and removed find sources variable length encoding news newspapers books scholar jstor december 2009 learn how and when to remove this message in coding theory variable length encoding is a symbol encoding scheme in which codes of differing lengths are used to encode symbols for representation through a communication channel or in a storage medium 1 the equivalent concept in computer science is bit string variable length codes can allow sources to be compressed and decompressed with zero error lossless data compression and still be read back symbol by symbol an independent and identically distributed source may be compressed almost arbitrarily close to its entropy this is in contrast to fixed length coding methods for which data compression is only possible for large blocks of data and any compression beyond the logarithm of the total number of possibilities comes with a finite though perhaps arbitrarily small probability of failure for these reasons they were sometimes used to pack english text into fewer bytes in adventure games for early microcomputers however disks increases in computer memory and general purpose compression algorithms have rendered such methods obsolete multibyte encodings are usually the result of a need to increase the number of characters which can be encoded without breaking backward compatibility with an existing constraint for example with one byte 8 bits per character one can encode 256 possible characters in order to encode more than 256 characters the obvious choice would be to use two or more bytes per encoding unit two bytes 16 bits would allow 65 536 possible characters but such a change would break compatibility with existing systems and therefore might not be feasible at all a unlikely source symbols can be assigned longer codewords while likely source symbols can be assigned shorter codewords thus giving a low expected codeword length some examples of well known variable length coding strategies are huffman coding lempel ziv coding arithmetic coding and context adaptive variable length coding general structure edit a multibyte encoding system minimises disruption to existing software by keeping some characters as single unit codes while others require multiple units this creates three unit types singletons which consist of a single unit lead units which come first in a multiunit sequence and trail units which come afterwards in a multiunit sequence input and display systems must handle these structures though most other software does not for example the four character string i ny is encoded in utf 8 like this shown as hexadecimal byte values 49 e2 99 a5 4e 59 of the six units in that sequence 49 4e and 59 are singletons for i n and y e2 is a lead unit and 99 and a5 are trail units the heart symbol is represented by the combination of the lead unit and the two trail units utf 8 clearly distinguishes singletons leads and trails with non overlapping value ranges by contrast older encodings often reuse values making it harder to parse text correctly this can cause false positives in searches or make a corrupted byte disrupt long sequences in well designed encodings like utf 8 searching works reliably and corruption affects only the character containing the bad unit codes and their extensions edit the extension of a code is the mapping of finite length source sequences to finite length bit strings that is obtained by concatenating for each symbol of the source sequence the corresponding codeword produced by the original code using terms from formal language theory the precise mathematical definition is as follows let s displaystyle s and t displaystyle t be two finite sets called the source and target alphabets respectively a code c s t displaystyle c s to t is a total function 2 mapping each symbol from s displaystyle s to a sequence of symbols over t displaystyle t and the extension of c displaystyle c to a homomorphism of s displaystyle s into t displaystyle t which naturally maps each sequence of source symbols to a sequence of target symbols is referred to as its extension variable length codes can be strictly nested in order of decreasing generality as non singular codes uniquely decodable codes and prefix codes prefix codes are always uniquely decodable and these in turn are always non singular non singular codes edit a code is non singular if each source symbol is mapped to a different non empty bit string that is the mapping from source symbols to bit strings is injective for example the mapping m 1 a 0 b 0 c 1 displaystyle m_ 1 texttt a mapsto texttt 0 texttt b mapsto texttt 0 texttt c mapsto texttt 1 is not non singular because both a and b map to the same bit string 0 any extension of this mapping will generate a lossy non lossless coding such singular coding may still be useful when some loss of information is acceptable for example when such code is used in audio or video compression where a lossy coding becomes equivalent to source quantization however the mapping m 2 a 1 b 011 c 01110 d 1110 e 10011 f 0 displaystyle m_ 2 texttt a mapsto texttt 1 texttt b mapsto texttt 011 texttt c mapsto texttt 01110 texttt d mapsto texttt 1110 texttt e mapsto texttt 10011 texttt f mapsto texttt 0 is non singular its extension will generate a lossless coding which will be useful for general data transmission but this feature is not always required it is not necessary for the non singular code to be more compact than the source and in many applications a larger code is useful for example as a way to detect or recover from encoding or transmission errors or in security applications to protect a source from undetectable tampering uniquely decodable codes edit a code is uniquely decodable if its extension is non singular whether a given code is uniquely decodable can be decided with the sardinas patterson algorithm the mapping m 3 a 0 b 01 c 011 displaystyle m_ 3 texttt a mapsto texttt 0 texttt b mapsto texttt 01 texttt c mapsto texttt 011 is uniquely decodable this can be demonstrated by looking at the follow set after each target bit string in the map because each bitstring is terminated as soon as we see a 0 displaystyle texttt 0 bit which cannot follow any existing code to create a longer valid code in the map but unambiguously starts a new code consider again the code m 2 displaystyle m_ 2 from the previous section 2 this code is not uniquely decodable since the string 011101110011 can be interpreted as the sequence of codewords 01110 1110 011 but also as the sequence of codewords 011 1 011 10011 two possible decodings of this encoded string are thus given by cdb and babe however such a code is useful when the set of all possible source symbols is completely known and finite or when there are restrictions such as a formal syntax that determine if source elements of this extension are acceptable such restrictions permit the decoding of the original message by checking which of the possible source symbols mapped to the same symbol are valid under those restrictions prefix codes edit main article prefix code a code is a prefix code if no target bit string in the mapping is a prefix of the target bit string of a different source symbol in the same mapping this means that symbols can be decoded instantaneously after their entire codeword is received other commonly used names for this concept are prefix free code instantaneous code or context free code a special case of prefix codes are block codes leb128 and variable length quantity vlq codes for example the mapping m 3 displaystyle m_ 3 above is not a prefix code because we do not know after reading the bit string 0 whether it encodes an a source symbol or if it is the prefix of the encodings of the b or c symbols an example of a prefix code is shown below symbol codeword a 0 b 10 c 110 d 111 example of encoding and decoding aabacdab 00100110111010 0 0 10 0 110 111 0 10 aabacdab for this example if the probabilities of a b c d displaystyle texttt a texttt b texttt c texttt d were 1 2 1 4 1 8 1 8 displaystyle textstyle left frac 1 2 frac 1 4 frac 1 8 frac 1 8 right the expected number of bits used to represent a source symbol using the code above would be 1 1 2 2 1 4 3 1 8 3 1 8 7 4 displaystyle 1 times frac 1 2 2 times frac 1 4 3 times frac 1 8 3 times frac 1 8 frac 7 4 as the entropy of this source is 1 75 bits per symbol this code compresses the source as much as possible so that the source can be recovered with zero error see also edit golomb code kruskal count instruction set architecture instruction length in computing wchar_t wide characters lotus multi byte character set lmbcs triple byte character set tbcs double byte character set dbcs single byte character set sbcs notes edit as a real life example of this utf 16 which represents the most common characters in exactly the manner just described and uses pairs of 16 bit code units for less common characters never gained traction as an encoding for text intended for interchange due to its incompatibility with the ubiquitous 7 8 bit ascii encoding with its intended role instead being taken by utf 8 which does preserve ascii compatibility references edit crispin m 2005 04 01 utf 9 and utf 18 efficient transformation formats of unicode ietf doi 10 17487 rfc4042 1 2 this code is based on an example found in berstel et al 2009 example 2 3 1 p 63 further reading edit salomon david september 2007 variable length codes for data compression 1 ed springer verlag isbn 978 1 84628 958 3 xii 191 pages errata 1 errata 2 berstel jean perrin dominique reutenauer christophe 2010 codes and automata encyclopedia of mathematics and its applications vol 129 cambridge uk cambridge university press isbn 978 0 521 88831 8 zbl 1187 94001 draft available online v t e data compression methods lossless type entropy adaptive coding arithmetic asymmetric numeral systems golomb huffman adaptive canonical modified range shannon shannon fano shannon fano elias tunstall unary universal exp golomb fibonacci gamma levenshtein dictionary byte pair encoding lempel ziv 842 lz4 lzjb lzo lzrw lzss lzw lzwl snappy other bwt ctw cm delta incremental dmc dpcm grammar re pair sequitur ldct mtf paq ppm rle hybrid lz77 huffman deflate lzx lzs lz77 ans lzfse lz77 huffman ans zstandard lz77 huffman context brotli lzss huffman lha lzh lz77 range lzma lzham rle bwt mtf huffman bzip2 lossy type transform discrete cosine transform dct mdct dst fft wavelet daubechies dwt spiht predictive dpcm adpcm lpc acelp celp lar lsp wlpc motion compensation estimation vector psychoacoustic audio concepts bit rate abr cbr vbr companding convolution dynamic range latency nyquist shannon theorem sampling silence compression sound quality speech coding sub band coding codec parts a law μ law dpcm adpcm dm ft fft lpc acelp celp lar lsp wlpc mdct psychoacoustic model image concepts chroma subsampling coding tree unit color space compression artifact image resolution macroblock pixel psnr quantization standard test image texture compression methods chain code dct deflate fractal klt lp rle wavelet daubechies dwt ezw spiht video concepts bit rate abr cbr vbr display resolution frame frame rate frame types interlace video characteristics video quality codec parts dct dpcm deblocking filter lapped transform motion compensation estimation vector wavelet daubechies dwt theory compressed data structures compressed suffix array fm index entropy information theory timeline kolmogorov complexity prefix code quantization rate distortion redundancy symmetry smallest grammar problem community hutter prize people mark adler david a huffman phil katz retrieved from https en wikipedia org w index php title variable length_encoding oldid 1365342874 categories coding theory entropy coding data compression hidden categories articles with short description short description is different from wikidata use dmy dates from december 2021 articles needing additional references from december 2009 all articles needing additional references this page was last edited on 21 july 2026 at 20 28 utc page was rendered with parsoid text is available under the creative commons attribution sharealike 4 0 license additional terms may apply by using this site you agree to the terms of use and privacy policy wikipedia is a registered trademark of the wikimedia foundation inc a non profit organization privacy policy about wikipedia disclaimers contact wikipedia legal safety contacts code of conduct developers statistics cookie statement mobile view search search toggle the table of contents variable length encoding 5 languages add topic