Misplaced Pages

#690309

71-576: WAV is an application of the Resource Interchange File Format (RIFF) bitstream format method for storing data in chunks , and thus is similar to the 8SVX and the Audio Interchange File Format (AIFF) format used on Amiga and Macintosh computers, respectively. The WAV file is an instance of a Resource Interchange File Format (RIFF) defined by IBM and Microsoft . The RIFF format acts as

142-419: A WAVE_FORMAT_EXTENSIBLE header was defined which specifies multiple audio channel data along with speaker positions, eliminates ambiguity regarding sample types and container sizes in the standard WAV format and supports defining custom extensions to the format. A RIFF file is a tagged file format. It has a specific container format (a chunk ) with a header that includes a four-character tag ( FourCC ) and

213-407: A wrapper for various audio coding formats . Though a WAV file can contain compressed audio, the most common WAV audio format is uncompressed audio in the linear pulse-code modulation (LPCM) format. LPCM is also the standard audio coding format for audio CDs , which store two-channel LPCM audio sampled at 44.1 kHz with 16 bits per sample . Since LPCM is uncompressed and retains all of

284-513: A WAVE file." The specification suggests a LIST chunk is also a sequence: "A LIST chunk contains a list, or ordered sequence, of subchunks." However, the specification does not give a formal specification of the INFO chunk; an example INFO LIST chunk ignores the chunk sequence implied in the INFO description. The LIST chunk definition for <wave-data> does use the LIST chunk as

355-425: A base case, or testing for it incorrectly, can cause an infinite loop . For some functions (such as one that computes the series for e = 1/0! + 1/1! + 1/2! + 1/3! + ... ) there is not an obvious base case implied by the input data; for these one may add a parameter (such as the number of terms to be added, in our series example) to provide a 'stopping criterion' that establishes the base case. Such an example

426-402: A container. RIFF files consist entirely of " chunks ". The overall format is identical to IFF , except for the endianness as previously stated, and the different meaning of the chunk names. All chunks have the following format: Two chunk identifiers, "RIFF" and "LIST", introduce a chunk that can contain subchunks. The RIFF and LIST chunk data (appearing after the identifier and length) have

497-523: A depth-first search. Single recursion is often much more efficient than multiple recursion, and can generally be replaced by an iterative computation, running in linear time and requiring constant space. Multiple recursion, by contrast, may require exponential time and space, and is more fundamentally recursive, not being able to be replaced by iteration without an explicit stack. Multiple recursion can sometimes be converted to single recursion (and, if desired, thence to iteration). For example, while computing

568-495: A group of samples (e.g., caption information). Finally, the mandatory <wave-data> chunk contains the actual samples in the format previously specified. Note that the WAV file definition does not show where an INFO chunk should be placed. It is also silent about the placement of a CSET chunk (which specifies the character set used). The RIFF specification attempts to be a formal specification, but its formalism lacks

639-408: A hybrid merge sort/insertion sort. Recursion and iteration are equally expressive: recursion can be replaced by iteration with an explicit call stack , while iteration can be replaced with tail recursion . Which approach is preferable depends on the problem under consideration and the language used. In imperative programming , iteration is preferred, particularly for simple recursion, as it avoids

710-509: A natural number), functions such as factorial may also be regarded as structural recursion. Generative recursion is the alternative: Many well-known recursive algorithms generate an entirely new piece of data from the given data and recur on it. HtDP ( How to Design Programs ) refers to this kind as generative recursion. Examples of generative recursion include: gcd , quicksort , binary search , mergesort , Newton's method , fractals , and adaptive integration . This distinction

781-421: A programming technique, it is used most often in the context of lazy programming languages, and can be preferable to recursion when the desired size or precision of a program's output is unknown. In such cases the program requires both a definition for an infinitely large (or infinitely precise) result, and a mechanism for taking a finite portion of that result. The problem of computing the first n prime numbers

SECTION 10

#1732772706691

852-459: A sequence container with good formal semantics. The WAV specification supports, and most WAV files use, a single contiguous array of audio samples. The specification also supports discrete blocks of samples and silence that are played in order. The specification for the sample data contains apparent errors: Apparently <data-list> (undefined) and <wave-list> (defined but not referenced) should be identical. Even with this resolved,

923-462: A set of three or more functions that call each other can be called a set of mutually recursive functions. Recursion is usually done by explicitly calling a function by name. However, recursion can also be done via implicitly calling a function based on the current context, which is particularly useful for anonymous functions , and is known as anonymous recursion . Some authors classify recursion as either "structural" or "generative". The distinction

994-469: A similar PAD chunk. The top-level definition of a WAV file is: The top-level RIFF form uses a WAVE tag. It is followed by a mandatory <fmt-ck> chunk that describes the format of the sample data that follows. This chunk includes information such as the sample encoding, number of bits per channel, the number of channels, and the sample rate. The WAV specification includes some optional features. The optional <fact-ck> chunk reports

1065-402: A single expression. A coinductive data definition is one that specifies the operations that may be performed on a piece of data; typically, self-referential coinductive definitions are used for data structures of infinite size. A coinductive definition of infinite streams of strings, given informally, might look like this: This is very similar to an inductive definition of lists of strings;

1136-439: A structure that contains a string and a list of strings. The self-reference in the definition permits the construction of lists of any (finite) number of strings. Another example of inductive definition is the natural numbers (or positive integers ): Similarly recursive definitions are often used to model the structure of expressions and statements in programming languages. Language designers often express grammars in

1207-471: A syntax such as Backus–Naur form ; here is such a grammar, for a simple language of arithmetic expressions with multiplication and addition: This says that an expression is either a number, a product of two expressions, or a sum of two expressions. By recursively referring to expressions in the second and third lines, the grammar permits arbitrarily complicated arithmetic expressions such as (5 * ((3 * 6) + 8)) , with more than one product or sum operation in

1278-522: A tree, which can be linear in the number of function calls, hence significant savings for O ( n ) algorithms; this is illustrated below for a depth-first search. Short-circuiting on a tree corresponds to considering a leaf (non-empty node with no children) as the base case, rather than considering an empty node as the base case. If there is only a single base case, such as in computing the factorial, short-circuiting provides only O (1) savings. Conceptually, short-circuiting can be considered to either have

1349-449: A wrapper function for the case when the overall recursion starts with the base case itself. For example, in the factorial function, properly the base case is 0! = 1, while immediately returning 1 for 1! is a short circuit, and may miss 0; this can be mitigated by a wrapper function. The box shows C code to shortcut factorial cases 0 and 1. Short-circuiting is primarily a concern when many base cases are encountered, such as Null pointers in

1420-408: Is BWF -compatible and allows file sizes to exceed 4 gigabytes . It does so by providing a "ds64" chunk with a 64-bit (8-byte) size. The optional INFO chunk allows RIFF files to be "tagged" with information falling into a number of predefined categories, such as copyright ("ICOP"), comments ("ICMT"), artist ("IART"), in a standardised way. These details can be read from a RIFF file even if the rest of

1491-418: Is a generic file container format for storing data in tagged chunks . It is primarily used for audio and video, though it can be used for arbitrary data. The Microsoft implementation is mostly known through container formats like AVI , ANI and WAV , which use RIFF as their basis. RIFF was introduced in 1991 by Microsoft and IBM and used as the default format for Windows 3.1 multimedia files. It

SECTION 20

#1732772706691

1562-454: Is also called mutual recursion , which is a more symmetric term, though this is simply a difference of emphasis, not a different notion. That is, if f calls g and then g calls f, which in turn calls g again, from the point of view of f alone, f is indirectly recursing, while from the point of view of g alone, it is indirectly recursing, while from the point of view of both, f and g are mutually recursing on each other. Similarly

1633-683: Is based on Interchange File Format introduced by Electronic Arts in 1985 on the Amiga . IFF uses the big-endian convention of the Amiga's Motorola 68000 CPU, but in RIFF multi- byte integers are stored in the little-endian order of the x86 processors used in IBM PC compatibles . A RIFX format, which is big-endian, was also introduced. In 2010 Google introduced the WebP picture format, which uses RIFF as

1704-407: Is generally less efficient , and, for certain problems, algorithmic or compiler-optimization techniques such as tail call optimization may improve computational performance over a naive recursive implementation. A common algorithm design tactic is to divide a problem into sub-problems of the same type as the original, solve those sub-problems, and combine the results. This is often referred to as

1775-476: Is important in proving termination of a function. In actual implementation, rather than a pure recursive function (single check for base case, otherwise recursive step), a number of modifications may be made, for purposes of clarity or efficiency. These include: On the basis of elegance, wrapper functions are generally approved, while short-circuiting the base case is frowned upon, particularly in academia. Hybrid algorithms are often used for efficiency, to reduce

1846-403: Is limited to files that are less than 4  GiB , because of its use of a 32-bit unsigned integer to record the file size in the header. Although this is equivalent to about 6.8 hours of CD-quality audio at 44.1 kHz, 16-bit stereo , it is sometimes necessary to exceed this limit, especially when greater sampling rates , bit resolutions or channel count are required. The W64 format

1917-415: Is more naturally treated by corecursion , where successive terms in the output are the partial sums; this can be converted to a recursion by using the indexing parameter to say "compute the n th term ( n th partial sum)". Many computer programs must process or generate an arbitrarily large quantity of data . Recursion is a technique for representing data whose exact size is unknown to the programmer :

1988-611: Is one of the central ideas of computer science. The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions. Most computer programming languages support recursion by allowing a function to call itself from within its own code. Some functional programming languages (for instance, Clojure ) do not define any looping constructs but rely solely on recursion to repeatedly call code. It

2059-462: Is one that can be solved with a corecursive program (e.g. here ). Recursion that contains only a single self-reference is known as single recursion , while recursion that contains multiple self-references is known as multiple recursion . Standard examples of single recursion include list traversal, such as in a linear search, or computing the factorial function, while standard examples of multiple recursion include tree traversal , such as in

2130-494: Is proved in computability theory that these recursive-only languages are Turing complete ; this means that they are as powerful (they can be used to solve the same problems) as imperative languages based on control structures such as while and for . Repeatedly calling a function from within itself may cause the call stack to have a size equal to the sum of the input sizes of all involved calls. It follows that, for problems that can be solved easily by iteration, recursion

2201-464: Is related to where a recursive procedure gets the data that it works on, and how it processes that data: [Functions that consume structured data] typically decompose their arguments into their immediate structural components and then process those components. If one of the immediate components belongs to the same class of data as the input, the function is recursive. For that reason, we refer to these functions as (STRUCTURALLY) RECURSIVE FUNCTIONS. Thus,

WAV - Misplaced Pages Continue

2272-422: Is uncommon except among video, music and audio professionals. The high resolution of the format makes it suitable for retaining first generation archived files of high quality, for use on a system where disk space and network bandwidth are not constraints. In spite of their large size, uncompressed WAV files are used by most radio broadcasters, especially those that have adopted a tapeless system. The WAV format

2343-481: The divide-and-conquer method ; when combined with a lookup table that stores the results of previously solved sub-problems (to avoid solving them repeatedly and incurring extra computation time), it can be referred to as dynamic programming or memoization . A recursive function definition has one or more base cases , meaning input(s) for which the function produces a result trivially (without recurring), and one or more recursive cases , meaning input(s) for which

2414-599: The Fibonacci sequence naively entails multiple iteration, as each value requires two previous values, it can be computed by single recursion by passing two successive values as parameters. This is more naturally framed as corecursion, building up from the initial values, while tracking two successive values at each step – see corecursion: examples . A more sophisticated example involves using a threaded binary tree , which allows iterative tree traversal, rather than multiple recursion. Most basic examples of recursion, and most of

2485-515: The INFO chunk. In addition, WAV files can embed any kind of metadata, including but not limited to Extensible Metadata Platform (XMP) data or ID3 tags in extra chunks. The RIFF specification requires that applications ignore chunks they do not recognize and applications may not necessarily use this extra information. Uncompressed WAV files are large, so file sharing of WAV files over the Internet

2556-496: The RIFF-based MIDI file format, and used it as the basis of an "extended midifile" that also includes instrument data in " DLS " format, embedded within the same .RMI file. For cataloguing purposes, the optimal position for the INFO chunk is near the beginning of the file. However, since the INFO chunk is optional, it is often omitted from the detailed specifications of individual file formats, leading to some confusion over

2627-460: The audio-editing program Audacity encounters a .WAV file with end-placed INFO data, it will correctly identify and read the data, but on saving, will relocate the INFO chunk back to the file header. Although CorelDRAW 10 nominally uses a RIFF file structure, the program's initial release placed the INFO chunk at the end, so that any embedded preview bitmap would not be displayed under Windows' file manager by default. A "patch" utility supplied with

2698-412: The auxiliary function can be nested inside the wrapper function and use a shared scope. In the absence of nested functions, auxiliary functions are instead a separate function, if possible private (as they are not called directly), and information is shared with the wrapper function by using pass-by-reference . Short-circuiting the base case, also known as arm's-length recursion , consists of checking

2769-460: The base case before making a recursive call – i.e., checking if the next call will be the base case, instead of calling and then checking for the base case. Short-circuiting is particularly done for efficiency reasons, to avoid the overhead of a function call that immediately returns. Note that since the base case has already been checked for (immediately before the recursive step), it does not need to be checked for separately, but one does need to use

2840-436: The base case check before the recursive step. Alternatively, these can be considered a different form of base case and recursive step, respectively. Note that this requires a wrapper function to handle the case when the tree itself is empty (root node is Null). In the case of a perfect binary tree of height h, there are 2 −1 nodes and 2 Null pointers as children (2 for each of the 2 leaves), so short-circuiting cuts

2911-410: The case of a WAV file, the additional tag is WAVE . The remainder of the RIFF data is a sequence of chunks describing the audio information. The advantage of a tagged file format is that the format can be extended later while maintaining backward compatibility . The rule for a RIFF (or WAV) reader is that it should ignore any tagged chunk that it does not recognize. The reader will not be able to use

WAV - Misplaced Pages Continue

2982-428: The clear separation of base case and recursive step in standard recursion, it is often considered poor style, particularly in academia. A basic example of short-circuiting is given in depth-first search (DFS) of a binary tree; see binary trees section for standard recursive discussion. The standard recursive algorithm for a DFS is: In short-circuiting, this is instead: In terms of the standard steps, this moves

3053-412: The correct position for this chunk within a file. When dealing with large media files, the expansion or contraction of the INFO chunk during tag-editing can result in the following "data" section of the file having to be read and rewritten back to disk to accommodate the new header size. Since media files can be gigabytes in size, this is a potentially disk-intensive process. One workaround is to "pad out"

3124-404: The defining characteristic of a structurally recursive function is that the argument to each recursive call is the content of a field of the original input. Structural recursion includes nearly all tree traversals, including XML processing, binary tree creation and search, etc. By considering the algebraic structure of the natural numbers (that is, a natural number is either zero or the successor of

3195-417: The difference is that this definition specifies how to access the contents of the data structure—namely, via the accessor functions head and tail —and what those contents may be, whereas the inductive definition specifies how to create the structure and what it may be created from. Corecursion is related to coinduction, and can be used to compute particular instances of (possibly) infinite objects. As

3266-552: The examples presented here, demonstrate direct recursion , in which a function calls itself. Indirect recursion occurs when a function is called not by itself but by another function that it called (either directly or indirectly). For example, if f calls f, that is direct recursion, but if f calls g which calls f, then that is indirect recursion of f. Chains of three or more functions are possible; for example, function 1 calls function 2, function 2 calls function 3, and function 3 calls function 1 again. Indirect recursion

3337-485: The existing MIDI file format used for storing song information to be played on electronic musical instruments. Microsoft's MIDI file format consisted of a standard MIDI file enclosed in a RIFF wrapper, and had the file extension .RMI . Since the existing MIDI file format already supported embedded "tagging" information, this caused the disadvantage of having to deal with two file formats for the same type of information. The MIDI Manufacturers Association have since embraced

3408-406: The file format is unrecognized. The standard also allows the use of user-defined fields. Programmers intending to use non-standard fields should bear in mind that the same non-standard subchunk ID may be used by different applications in different (and potentially incompatible) ways. In line with their policy of using .RIFF for all Windows 3.1 "multimedia" files, Microsoft introduced a new variant on

3479-495: The file size. All WAV files; even those that use MP3 compression use the .wav extension. This is a reference to compare the monophonic (not stereophonic ) audio quality and compression bitrates of audio coding formats available for WAV files including LPCM, ADPCM , Microsoft GSM 06.10 , CELP , SBC , Truespeech and MPEG Layer-3. These are the default ACM codecs that come with Windows. Resource Interchange File Format Resource Interchange File Format ( RIFF )

3550-565: The following format: The file itself consists of one RIFF chunk, which then can contain further subchunks: hence, the first four bytes of a correctly formatted RIFF file will spell out "RIFF". More information about the RIFF format can be found in the Interchange File Format article. RF64 is a multichannel file format based on RIFF specification, developed by the European Broadcasting Union . It

3621-423: The full-scale range representing ±1  V or A rather than a sound pressure. Audio compact discs (CDs) do not use the WAV file format, using instead Red Book audio . The commonality is that audio CDs are encoded as uncompressed 16-bit 44.1 kHz stereo LPCM, which is one of the formats supported by WAV. Audio in WAV files can be encoded in a variety of audio coding formats, such as GSM or MP3 , to reduce

SECTION 50

#1732772706691

3692-422: The leading INFO chunk using dummy data (using a "dummy chunk" or "pad chunk") when the file is created. Later editing can then expand or contract the "dummy" field to keep the total size of the file header constant: an intelligently written piece of software can then overwrite just the file header when tagging data is changed, without modifying or moving the main body of the file. Some programs have tried to address

3763-456: The new information, but the reader should not be confused. The specification for RIFF files includes the definition of an INFO chunk. The chunk may include information such as the title of the work, the author, the creation date, and copyright information. Although the INFO chunk was defined for RIFF in version 1.0, the chunk was not referenced in the formal specification of a WAV file. Many readers had trouble processing this. Consequently,

3834-505: The number of function calls in half in the worst case. In C, the standard recursive algorithm may be implemented as: The short-circuited algorithm may be implemented as: Note the use of short-circuit evaluation of the Boolean && (AND) operators, so that the recursive call is made only if the node is valid (non-Null). Note that while the first term in the AND is a pointer to a node,

3905-421: The number of samples for some compressed coding schemes. The <cue-ck> chunk identifies some significant sample numbers in the wave file. The <playlist-ck> chunk allows the samples to be played out of order or repeated rather than just from beginning to end. The associated data list ( <assoc-data-list> ) allows labels and notes to be attached to cue points; text annotation may be given for

3976-618: The overhead of recursion in small cases, and arm's-length recursion is a special case of this. A wrapper function is a function that is directly called but does not recurse itself, instead calling a separate auxiliary function which actually does the recursion. Wrapper functions can be used to validate parameters (so the recursive function can skip these), perform initialization (allocate memory, initialize variables), particularly for auxiliary variables such as "level of recursion" or partial computations for memoization , and handle exceptions and errors. In languages that support nested functions ,

4047-556: The overhead of repeated function calls and returns. For this reason efficient implementations of recursive algorithms often start with the recursive algorithm, but then switch to a different algorithm when the input becomes small. An important example is merge sort , which is often implemented by switching to the non-recursive insertion sort when the data is sufficiently small, as in the tiled merge sort . Hybrid recursive algorithms can often be further refined, as in Timsort , derived from

4118-454: The precision seen in other tagged formats. For example, the RIFF specification does not clearly distinguish between a set of subchunks and an ordered sequence of subchunks. The RIFF form chunk suggests it should be a sequence container. Sequencing information is specified in the RIFF form of a WAV file consistent with the formalism: "However, <fmt-ck> must always occur before <wave-data> , and both of these chunks are mandatory in

4189-463: The problem by placing the INFO chunk at the end of a media file, after the main body of the file. This has resulted in two different conventions for chunk placement, with the attendant risk that some combinations of software can cause a file's INFO data to be ignored or permanently overwritten during editing. More sophisticated programs will take into account the possibility of "unexpected" chunk placement in files and respond accordingly. For instance, when

4260-460: The productions then allow a <data-ck> to contain a recursive <wave-data> (which implies data interpretation problems). To avoid the recursion, the specification can be interpreted as: WAV files can contain embedded IFF lists , which can contain several sub-chunks . This is an example of a WAV file header (44 bytes). Data is stored in little-endian byte order. As a derivative of RIFF, WAV files can be tagged with metadata in

4331-587: The program fixes this problem. RIFF information tags are found in WAV audio and AVI video files. The field consists of two values (v[0] and v[1]) separated with a space (0x20). Sample code: Recursion (computer science) In computer science , recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves such recursive problems by using functions that call themselves from within their own code. The approach can be applied to many types of problems, and recursion

SECTION 60

#1732772706691

4402-423: The program recurs (calls itself). For example, the factorial function can be defined recursively by the equations 0! = 1 and, for all n > 0 , n ! = n ( n − 1)! . Neither equation by itself constitutes a complete definition; the first is the base case, and the second is the recursive case. Because the base case breaks the chain of recursion, it is sometimes also called the "terminating case". The job of

4473-438: The programmer can specify this data with a self-referential definition. There are two types of self-referential definitions: inductive and coinductive definitions. An inductively defined recursive data definition is one that specifies how to construct instances of the data. For example, linked lists can be defined inductively (here, using Haskell syntax): The code above specifies a list of strings to be either empty, or

4544-420: The recursive cases can be seen as breaking down complex inputs into simpler ones. In a properly designed recursive function, with each recursive call, the input problem must be simplified in such a way that eventually the base case must be reached. (Functions that are not intended to terminate under normal circumstances—for example, some system and server processes —are an exception to this.) Neglecting to write

4615-456: The safest thing to do from an interchange standpoint was to omit the INFO chunk and other extensions and send a lowest-common-denominator file. There are other INFO chunk placement problems . RIFF files were expected to be used in international environments, so there is CSET chunk to specify the country code, language, dialect, and code page for the strings in a RIFF file. For example, specifying an appropriate CSET chunk should allow

4686-400: The same base case and recursive step, checking the base case only before the recursion, or it can be considered to have a different base case (one step removed from standard base case) and a more complex recursive step, namely "check valid then recurse", as in considering leaf nodes rather than Null nodes as base cases in a tree. Because short-circuiting has a more complicated flow, compared with

4757-629: The samples of an audio track, professional users or audio experts may use the WAV format with LPCM audio for maximum audio quality. WAV files can also be edited and manipulated with relative ease using software. On Microsoft Windows, the WAV format supports compressed audio using the Audio Compression Manager (ACM). Any ACM codec can be used to compress a WAV file. The user interface (UI) for ACM may be accessed through various programs that use it, including Sound Recorder in some versions of Windows. Beginning with Windows 2000 ,

4828-519: The second term is a Boolean, so the overall expression evaluates to a Boolean. This is a common idiom in recursive short-circuiting. This is in addition to the short-circuit evaluation of the Boolean || (OR) operator, to only check the right child if the left child fails. In fact, the entire control flow of these functions can be replaced with a single Boolean expression in a return statement, but legibility suffers at no benefit to efficiency. Recursive algorithms are often inefficient for small data, due to

4899-407: The size (number of bytes) of the chunk. The tag specifies how the data within the chunk should be interpreted, and there are several standard FourCC tags. Tags consisting of all capital letters are reserved tags. The outermost chunk of a RIFF file has a RIFF tag; the first four bytes of chunk data are an additional FourCC tag that specify the form type and are followed by a sequence of subchunks. In

4970-429: The strings in an INFO chunk (and other chunks throughout the RIFF file) to be interpreted as Cyrillic or Japanese characters. RIFF also defines a JUNK chunk whose contents are uninteresting. The chunk allows a chunk to be deleted by just changing its FourCC. The chunk could also be used to reserve some space for future edits so the file could be modified without being resized. A later definition of RIFF introduced

5041-622: Was therefore created for use in Sound Forge . Its 64-bit file size field in the header allows for much longer recording times. The RF64 format specified by the European Broadcasting Union has also been created to solve this problem. Since the sampling rate of a WAV file can vary from 1  Hz to 4.3  GHz , and the number of channels can be as high as 65535, WAV files have also been used for non-audio data. LTspice , for instance, can store multiple circuit trace waveforms in separate channels, at any appropriate sampling rate, with

#690309