text:
# Flavor: A Language for Media Representation

## 1 Introduction

Flavor originated from the need to simplify and speed up the development of software that processes coded audio-visual or general multimedia information. This includes encoders and decoders as well as applications that manipulate such information. Examples include editing tools, synthetic content creation tools, multimedia indexing and search engines, etc. Such information is invariably encoded in a highly efficient form to minimize the cost of storage and transmission. This source coding  operation is almost always performed in a bitstream-oriented fashion: the data to be represented is converted to a sequence of binary values of arbitrary (and typically variable) lengths, according to a specified syntax. The syntax itself can have various degrees of sophistication. One of the simplest forms is the GIF87a format , consisting of essentially two headers and blocks of coded image data using the Lempel-Ziv-Welch (LZW) compression. Much more complex formats include JPEG , MPEG-1 , MPEG-2  and MPEG-4 , among others.

General-purpose programming languages such as C++  and Java  do not provide native facilities for coping with such data. Software codec (encoder/decoder) or application developers need to build their own facilities, involving two components. First, they need to develop software that deals with the bitstream-oriented nature of the data, as general-purpose microprocessors are strictly byte-oriented. Second, they need to implement parsing and generation code that complies with the syntax of the format at hand (be it proprietary or standard). These two tasks represent a significant amount of the overall development effort. They also have to be duplicated by everyone who requires access to a particular compressed representation within their application. Furthermore, they can also represent a substantial percentage of the overall execution time of the application.

Flavor addresses these problems in an integrated way. First, it allows the “formal” description of the bitstream syntax. Formal here means that the description is based on a well-defined grammar, and as a result is amenable to software tool manipulation. In the past, such descriptions were using ad-hoc conventions involving tabular data or pseudo-code. A second and key aspect of Flavor’s architecture is that this description has been designed as an extension of C++ and Java, both heavily used object-oriented languages in multimedia applications development. This ensures seamless integration of Flavor code with both C++ and Java code and the overall architecture of an application.

Flavor was designed as an object-oriented language, anticipating an audio-visual world comprised of audio-visual objects, both synthetic and natural, and combining it with well-established paradigms for software design and implementation. Its object-oriented facilities go beyond the mere duplication of C++ and Java features, and introduce several new concepts that are pertinent for bitstream-based media representation.

In order to validate the expressive power of the language, several existing bitstream formats have already been described in Flavor, including sophisticated structures such as MPEG-2 Systems, Video and Audio. A translator has also been developed for translating Flavor code to C++ or Java code. We should note that Flavor is currently used in the Structured Audio as well as the Systems parts of the MPEG-4 standard.

Emerging multimedia representation techniques can directly use Flavor to represent the bitstream syntax in their specifications. This will allow immediate use of such specifications in new or existing applications, since the code to access/generate conforming data can be generated directly from the specification with zero cost. In addition, such code can be automatically optimized; this is particularly important for operations such as Huffman decoding/encoding, a very common tool in media representation.

In the following, we first present a brief background of the language in terms of its history and technical approach. We then describe each of its features, including declarations and constants, expressions and statements, classes, scoping rules, maps, and built-in operators. We also describe the translator and its simple run-time API. Finally, we conclude with an overview of the benefits of using the Flavor approach for media representation. More detailed information and publicly available software can be found in the Flavor web site at: http://flavor.sourceforge.net. Parts of this paper have been presented in .

## 2 Background

### 2.1 A Brief History

Flavor has its origins in a Perl script (mkvlc that was developed in early 1994 in order to automate the (laborious) generation of C code declarations for variable-length code (VLC) tables of the MPEG-2 Video specification111The mkvlc program is available at http://www.ee.columbia.edu/$``$eleft/software/mkvlc.tar.gz.. In November 1995, the ideas behind mkvlc took a more concrete shape in the form of a “syntactic description language,”  i.e., a formal way to describe not just VLCs, but the entire structure of a bitstream. Such a facility was proposed to the MPEG-4 standardization activity, which at that time had started to consider flexible, even programmable, audio-visual decoding systems. The language subsequently underwent a series of revisions obtaining input from several participants in the MPEG-4 standardization activity, and its specification is now fairly stable.

### 2.2 Technical Approach

Flavor provides a formal way to specify how data is laid out in a serialized bitstream. It is based on a principal of separation between bitstream parsing operations and encoding, decoding and other operations. This separation acknowledges the fact that the same syntax can be utilized by different tools, but also that the same tool can work unchanged with a different bitstream syntax. For example, the number of bits used for a specific field can change without modifying any part of the application program.

Past approaches for syntax description utilized a combination of tabular data, pseudo-code, and textual description to describe the format at hand. Taking MPEG as an example, both MPEG-1 and MPEG-2 specifications were described using a C-like pseudo-code syntax (originally introduced by Milt Anderson, Bellcore), coupled with explanatory text and tabular data. Several of the lower and most sophisticated layers (e.g., macroblock) could only be handled by explanatory text. The text had to be carefully crafted and tested over time for ambiguities. Other specifications (e.g., GIF and JPEG) use similar bitstream representation schemes, and hence share the same limitations.

Other formal facilities already exist for representing syntax. One example is ASN.1 (ISO International Standards 8824 and 8825). A key difference, however, is that ASN.1 was not designed to address the intricacies of source coding operations, and hence cannot cope with, for example, variable-length coding. In addition, ASN.1 tries to hide the bitsream representation from the developer by using its own set of binary encoding rules, whereas in our case the binary encoding is the actual target of description.

There is also some remote relationship between syntax description and “marshalling,” a fundamental operation in distributed systems where consistent exchange of typed data is ensured. Examples in this category include Sun’s ONC XDR (External Data Representation) and the rpcgen compiler which automatically generates marshalling code, as well as CORBA IDL, among others. These ensure, for example, that even if the native representation of an integer in two systems is different (big versus little endian), they can still exchange typed data in a consistent way. Marshalling, however, does not constitute bitstream syntax description because: 1) the programmer does not have control over the data representation (the binary representation for each data type is predefined), 2) it is only concerned with the representation of simple serial structures (lists of arguments to functions, etc.). As in ASN.1, the binary representation is “hidden” and is not amenable to customization by the developer. One could parallel Flavor and marshalling by considering the Flavor source as the XDR layer. A better parallelism would be to view Flavor as a parser-generator like yacc , but for bitstream representations.

It is interesting to note that all prior approaches to syntactic description were concerned only with the definition of message structures typically found in communication systems. These tend to have a much simpler structure compared with coded representations of audio-visual information (compare the UDP packet header with the baseline JPEG specification, for example).

A new language, Bitstream Syntax Description Language (BSDL) , has recently been introduced in MPEG-21  for describing the structure of a bitstream using XML Schema. However, unlike Flavor, BSDL is developed to address only the high-level structure of the bitstream, and it becomes almost impossible to fully describe the bitstream syntax on a bit-per-bit bases. For example, BSDL does not have a facility to cope with variable-length coding, whereas in Flavor, map (described in Section 3.5) can be used. Also, the BSDL description would be overly verbose, requiring a significant effect to review and modify the description with human eye.

Flavor was designed to be an intuitive and natural extension of the typing system of object-oriented languages like C++ and Java. This means that the bitstream representation information is placed together with the data declarations in a single place. In C++ and Java, this place is where a class is defined.

Flavor has been explicitly designed to follow a declarative approach to bitstream syntax specification. In other words, the designer is specifying how the data is laid out on the bitstream, and does not detail a step-by-step procedure that parses it. This latter procedural approach would severely limit both the expressive power as well as the capability for automated processing and optimization, as it would eliminate the necessary level of abstraction. As a result of this declarative approach, Flavor does not have functions or methods.

A related example from traditional programming is the handling of floating point numbers. The programmer does not have to specify how such numbers are represented or how operations are performed; these tasks are automatically taken care of by the compiler in coordination with the underlying hardware or run-time emulation libraries.

An additional feature of combining type declaration and bitstream representation is that the underlying object hierarchy of the base programming language (C++ or Java), becomes quite naturally the object hierarchy for bitstream representation purposes as well. This is an important benefit for ease of application development, and it also allows Flavor to have a very rich typing system itself.

HelloBits” - Traditionally, programming languages are introduced via a simple “Hello World!” program, which just prints out this simple message on the user’s terminal. We will use a similar example with Flavor, but here we are concerned about bits, rather than text characters. Figure 1 shows a set of trivial examples indicating how the integration of type and bitstream representation information is accomplished. Consider a simple object called HelloBits with just a single value, represented using 8 bits. Using the MPEG-1/2 methodology, this would be described as shown in Figure 1(a). A C++ description of this single-value object would include two methods to read and write its value, and have a form similar to the one shown in Figure 1(b). Here getuint() is assumed to be a function that reads bits from the bitstream (here 8) and returns them as an unsigned integer (the most significant bit first); the putuint() function has similar functionality but for output purposes. When HelloBits::get() is called, the bitstream is read and the resultant quantity is placed in the data member Bits. The same description in Flavor is shown in Figure 1(c).

As we can see, in Flavor the bitstream representation is integrated with the type declaration. The Flavor description should be read as: Bits is an unsigned integer quantity represented using 8 bits in the bitstream. Note that there is no implicit encoding rule as in ASN.1: the rule here is embedded in the type declaration and indicates that, when the system has to parse a HelloBits data type, it will just read the next 8 bits as an unsigned integer and assign them to the variable Bits.

These examples, although trivial, demonstrate the differences between the various approaches. In Figure 1(a), we just have a tabulation of the various bitstream entities, grouped into syntactic units. This style is sufficient for straightforward representations, but fails when more complex structures are used (e.g., VLCs). In Figure 1(b), the syntax is incorporated into hand-written code embedded in a get() and put() or an equivalent set of methods. As a result, the syntax becomes an integral part of the encoding/decoding method even though the same encoding/decoding mechanism could be applied to a large variety of similar syntactic constructs. Also, it quickly becomes overly verbose.

Flavor provides a wide range of facilities to define sophisticated bitstreams, including if-else, switch, for, and while constructs. In contrast with regular C++ or Java, these are all included in the data declaration part of the class, so they are completely disassociated from code that belongs to class methods. This is in line with the declarative nature of Flavor, where the focus is on defining the structure of the data, not operations on them. As we show later on, a translator can automatically generate C++ and/or Java methods (put() and get()) that can read or write data that complies to the Flavor-described representation.

In the following we describe each of the language features in more detail, emphasizing the differences between C++ and Java. In order to ensure that Flavor semantics are in line with both C++ and Java, whenever there was a conflict a common denominator approach was used.

## 3 Language Overview

### 3.1 Declarations and Constants

#### 3.1.1 Literals

All traditional C++ and Java literals are supported by Flavor. This includes integers, floating-point numbers and character constants (e.g., ‘a’). Strings are also supported by Flavor. They are converted to arrays, with or without a trailing ‘`\0`’ (null character).

Additionally, Flavor defines a special binary number notation using the prefix 0b. Numbers represented with such notation are called binary literals (or bit strings) and, in addition to the actual value, also convey their length. For example, one can write 0b011 to denote the number 3 represented using 3 bits. For readability, a bit string can include periods every four digits, e.g., 0b0010.01. Hexadecimal or octal constants used in the context of a bit string also convey their length in addition to their value. Whenever the length of a binary literal is irrelevant, it is treated as a regular integer literal.

#### 3.1.2 Comments

Both multi-line `(/**/)` and single-line `(//)` comments are allowed. The multi-line comment delimiters cannot be nested.

#### 3.1.3 Names

Variable names follow the C++ and Java conventions (e.g., variable names cannot start with a number). The keywords that are used in C++ and Java are considered reserved in Flavor.

#### 3.1.4 Types

Flavor supports the common subset of C++ and Java built-in or fundamental types. This includes char, int, float, and double along with all appropriate modifiers (short, long, signed and unsigned). Additionally, Flavor defines a new type called bit and a set of new modifiers, big and little. The type bit is used to accommodate bit string variables and the new modifiers are used to indicate the endianess of bytes. The big modifier is used to represent the numbers using big-endian byte ordering (the most significant byte first) and the little modifier is used for the numbers represented using the little-endian method. By default, big-endian byte ordering is assumed. Note that endianess here refers to the bitstream representation, not the processor on which Flavor software may be running. The latter is irrelevant for the bitstream description.

Flavor also allows declaration of new types in the form of classes (refer to Section 3.3 for more information regarding classes). However, Flavor does not support pointers, references, casts, or C++ operators related to pointers. Structures or enumerations are not supported either, since they are not supported by Java.

#### 3.1.5 Declarations

Regular variable declarations can be used in Flavor in the same way as in C++ and Java. As Flavor follows a declarative approach, constant variable declarations with specified values are allowed everywhere (there is no constructor to set the initial values). This means that the declaration ‘const int a = 1;’ is valid anywhere (not just in global scope). The two major differences are the declaration of parsable variables and arrays.

Parsable Variables

Parsable variables are the core of Flavor’s design; it is the proper definition of these variables that defines the bitstream syntax. Parsable variables include a parse length specification immediately after their type declaration, as shown in Figure 2. In Figure 2(a), the blength argument can be an integer constant, a non-constant variable of type compatible to int, or a map (discussed later on) with the same type as the variable. This means that the parse length of a variable can be controlled by another variable. For example, the parsable variable declaration in Figure 2(b) indicates that the variable a has the parse length of 3 bits. In addition to the parse length specification, parsable variables can also have the aligned modifier. This signifies that the variable begins at the next integer multiple boundary of the length argument - alength \- specified within the alignment expression. If this length is omitted, an alignment size of 8 is assumed (byte boundary). Thus, the variable a is byte-aligned and for parsing, any intermediate bits are ignored, while for output bitstream generation the bitstream is padded with zeroes.

As we will see later on, parsable variables cannot be assigned to. This ensures that the syntax is preserved regardless if we are performing an input or output operation. However, parsable variables can be redeclared, as long as their type remains the same, only the parse size is changed, and the original declaration was not as a const. This allows one to select the parse size depending on the context (see Expressions and Statements, Section 3.2). On top of this, they obey special scoping rules as described in Section 3.4.

In general, the parse size expression must be a non-negative value. The special value 0 can be used when, depending on the bitstream context, a variable is not present in the bitstream but obtains a default value. In this case, no bits will be parsed or generated, however, the semantics of the declaration will be preserved. The variables of type float, double, and long double are only allowed to have a parse size equal to the fixed size that their standard representation requires (32 and 64 bits).

Look-Ahead Parsing

In several instances, it is desirable to examine the immediately following bits in the bitstream without actually removing the bits from the input stream. To support this behavior, a ‘\*’ character can be placed after the parse size parentheses. Note that for bitstream output purposes, this has no effect. An example of a declaration of a variable for look-ahead parsing is given in Figure 2(c).

Parsable Variables with Expected Values

Very often, certain parsable variables in the syntax have to have specific values (markers, start codes, reserved bits, etc.). These are specified as initialization values for parsable variables. Figure 2(d) shows an example. The example is interpreted as: a is an integer represented with 3 bits, and must have the value 2. The keyword const may be prepended in the declaration, to indicate that the parsable variable will have this constant value and, as a result, cannot be redeclared.

As both parse size and initial value can be arbitrary expressions, we should note that the order of evaluation is parse expression first, followed by the initializing expression.

Arrays

Arrays have special behavior in Flavor, due to its declarative nature but also due to the desire for very dynamic type declarations. For example, we want to be able to declare a parsable array with different array sizes depending on the context. In addition, we may need to load the elements of an array one at a time (this is needed when the retrieved value indicates indirectly if further elements of the array should be parsed). These concerns are only relevant for parsable variables. The array size, then, does not have to be a constant expression (as in C++ and Java), but it can be a variable as well. The example in Figure 3(a) is allowed in Flavor.

An interesting question is how to handle initialization of arrays, or parsable arrays with expected values. In addition to the usual brace-expression initialization, Flavor also provides a mechanism that involves the specification of a single expression as the initializer as shown in Figure 3(b). This means that all elements of B will be initialized with the value 5. In order to provide more powerful semantics to array initialization, Flavor considers the parse size and initializer expressions as executed per each element of the array. The array size expression, however, is only executed once, before the parse size expression or the initializer expression.

Let’s look at a more complicated example in Figure 3(c). Here A is declared as an array of 2 integers. The first one is parsed with 3 bits and is expected to have the value 4, while the second is parsed with 5 bits and is expected to have the value 6. After the declaration, a is left with the value 6. This probably represents the largest deviation of Flavor’s design from C++ and Java declarations. On the other hand it does provide significant flexibility in constructing sophisticated declarations in a very compact form, and it is also in line with the dynamic nature of variable declarations that Flavor provides.

Partial Arrays

An additional refinement of array declaration is partial arrays. These are declarations of parsable arrays in which only a subset of the array needs to be declared (or, equivalently, parsed from or written to a bitstream). Flavor introduces a double bracket notation for this purpose. The example in Figure 3(d) demonstrates its use. In the first line, we are declaring the 4-th element of A (array indices start from 0). The array size is unknown at this point, but of course it will be considered at least 4. In the second line, we are declaring a two-dimensional array, and in particular only its third row (assuming the first index corresponds to a row). The array indices can, of course, be expressions themselves. Partial arrays can only appear on the left-hand side of declaration and are not allowed in expressions.

### 3.2 Expressions and Statements

Flavor supports all of the C++ and Java arithmetic, logical and assignment operators. However, parsable variables cannot be used as lvalues. This ensures that they always represent the bitstream’s content, and allow consistent operations for the translator-generated get() and put() methods that read and write, respectively, data according to the specified form. Refer to Section 4.1 for detailed information about these methods.

Flavor also supports all the familiar flow control statements: if-else, do-while, while, and switch. In contrast to C++ and Java, variable declarations are not allowed within the arguments of these statements (i.e., ‘for(int i=0; ; );’ is not allowed). This is because in C++ the scope of this variable will be the enclosing one (even though this is fixed in the new ANSI C++ standard, some compilers still use the older concept), while in Java it will be the enclosed one. To avoid confusion, we opted for the exclusion of both alternatives at the expense of a slightly more verbose notation. Scoping rules are discussed in detail in Section 3.4. Similarly, Java only allows Boolean expressions as part of the flow control statements, and statements like ‘if (1) { … }’ is not allowed in Java. Thus, only the flow control statements with boolean expressions are valid in Flavor.

Figure 4 shows an example of the use of these flow control statements. The variable b is declared with a parse size of 16 if a is equal to 1, and with a parse size of 24 otherwise. Observe that this construct would not be meaningful in C++ or Java as the two declarations would be considered as being in separate scopes. This is the reason why parsable variables need to obey slightly different scoping rules than regular variables. The way to approach this to avoid confusion is to consider that Flavor is designed so that these parsable variables have to be properly defined at the right time and position. All the rest of the code is there to ensure that this is the case. We can consider the parsable variable declarations as “actions” that our system will perform at the specified times. This difference, then, in the scoping rules becomes a very natural one.

### 3.3 Classes

Flavor uses the notion of classes in exactly the same way as C++ and Java do. It is the fundamental structure in which object data are organized. Keeping in line with the support of both C++ and Java-style programming, classes in Flavor cannot be nested, and only single inheritance is supported. In addition, due to the declarative nature of Flavor, methods are not allowed (this includes constructors and destructors as well).

Figure 5 shows an example of a simple class declaration with just two parsable member variables. The trailing ‘;’ character is optional accommodating both C++ and Java-style class declarations. This class defines objects which contain two parsable variables. They will be present in the bitstream in the same order they are declared. After this class is defined, we can declare objects of this type as follows: ‘SimpleClass a;’.

A class is considered parsable if it contains at least one variable that is parsable. Declaration of parsable class variables can be prepended by the aligned modifier in the same way as parsable variables.

Class member variables in Flavor do not require access modifiers (public, protected, or private). In essence, all such variables are considered public.

#### 3.3.1 Parameter Types

As Flavor classes cannot have constructors, it is necessary to have a mechanism to pass external information to a class. This is accomplished using parameter types. These act the same way as formal arguments in function or method declarations do. They are placed in parentheses after the name of the class. Figure 6 gives an example of a simple class declaration with parameter types. When declaring variables of parameter type classes, it is required that the actual arguments are provided in place of the formal ones as displayed in the figure.

Of course the types of the formal and actual parameters must match. For arrays, only their dimensions are relevant; their actual sizes are not significant as they can be dynamically varying. Note that class types are allowed in parameter declarations as well.

#### 3.3.2 Inheritance

As we mentioned earlier, Flavor supports single inheritance so that compatibility with Java is maintained. Although Java can “simulate” multiple inheritance through the use of interfaces, Flavor has no such facility (it would be meaningless since methods do not exist in Flavor). However, for media representation purposes, we have not found any instance where multiple inheritance would be required, or even be desirable. It is interesting to note that all existing representation standards today are not truly object-based. The only exception, to our knowledge, is the MPEG-4 specification that explicitly addresses the representation of audio-visual objects. It is, of course, possible to describe existing structures in an object-oriented way but it does not truly map one-to-one with the notion of objects. For example, the MPEG-2 Video slices can be considered as separate objects of the same type, but of course their semantic interpretation (horizontal stripes of macroblocks) is not very useful. Note that containment formats like MP4 (MPEG-4 Systems file format) and Apple’s Quick Time are more object-oriented, as they are composed of object-oriented structures called “atoms”.

Derivation in C++ and Java is accomplished using a different syntax (extends versus ‘:’). Here we opted for the Java notation (also ‘:’ is used for object identifier declarations as explained below). Unfortunately, it was not possible to satisfy both.

In Figure 7(a) we show a simple example of a derived class declaration. Derivation from a bitstream representation point of view means that B is an A with some additional information. In other words, the behavior would be almost identical if we just copied the statements between the braces in the declaration of A in the beginning of B. We say ‘almost’ here because scoping rules of variable declarations also come into play, as discussed in Section 3.4.

Note that if a class is derived from a parsable class, it is also considered parsable.

#### 3.3.3 Polymorphic Parsable Classes

The concept of inheritance in object-oriented programming derives its power from its capability to implement polymorphism. In other words, the capability to use a derived object in a place where an object of the base class is expected. Although the mere structural organization is useful as well, it could be accomplished equally well with containment (a variable of type A is the first member of B).

Polymorphism in traditional programming languages is made possible via vtable structures, which allow the resolution of operations during run-time. Such behavior is not pertinent for Flavor, as methods are not allowed.

A more fundamental issue, however, is that Flavor describes the bitstream syntax: the information with which the system can detect which object to select must be present in the bitstream. As a result, traditional inheritance as defined in the previous section does not allow the representation of polymorphic objects. Considering Figure 7(a), there is no way to figure out, by reading a bitstream, if we should read an object of type A or type B.

Flavor solves this problem by introducing the concept of object identifiers or IDs. The concept is rather simple: in order to detect which object we should parse/generate, there must be a parsable variable that will identify it. This variable must have a different expected value for any class derived from the originating base class, so that object resolution can be uniquely performed in a well-defined way (this can be checked by the translator). As a result, object ID values must be constant expressions and they are always considered constant, i.e., they cannot be redeclared within the class.

In order to signify the importance of the ID variables, they are declared immediately after the class name (including any derivation declaration) and before the class body. They are separated from the class name declaration using a colon (‘:’). We could rewrite the example of Figure 7(a) with IDs as shown in Figure 7(b). Upon reading the bitstream, if the next 1 bit has the value 0, an object of type A will be parsed; if the value is 1, then an object of type B will be parsed. For output purposes, and as will be discussed in Section 4, it is up to the user to set up the right object type in preparation for output.

The name and the type of the ID variable is irrelevant, and can be anything that the user chooses. It cannot, however, be an array or a class variable (only built-in types are allowed). Also, the name, type and parse size must be identical between the base and derived classes. However, object identifiers are not required for all derived classes of a base class that has a declared ID. In this case, only the derived classes with defined IDs can be used wherever the base class can appear. This type of polymorphism is already used in the MPEG-4 Systems specification, and in particular the Binary Format for Scenes (BIFS) . This is a VRML-derived set of nodes that represent objects and operations on them, thus forming a hierarchical description of a scene.

The ID of a class is also possible to have a range of possible values which is specified as start\_id …end\_id, inclusive of both bounds. See Figure 7(c) for example.

### 3.4 Scoping Rules

The scoping rules that Flavor uses are identical with C++ and Java with the exception of parsable variables. As in C++ and Java, a new scope is introduced with curly braces ({}). Since Flavor does not have functions or methods, a scope can either be the global one or a scope within a class declaration. Note that the global scope cannot contain any parsable variable, since it does not belong to any object. As a result, global variables can only be constants.

Within a class, all parsable variables are considered as class member variables, regardless of the scope they are encountered in. This is essential in order to allow conditional declarations of variables which will almost always require that the actual declarations occur within compound statements (see Figure 4). Non-parsable variables that occur in the top-most class scope are also considered class member variables. The rest live within their individual scopes.

This distinction is important in order to understand which variables are accessible to a class variable that is contained in another class. The issues are illustrated in Figure 8. Looking at the class A, the initial declaration of i occurs in the top-most class scope; as a result i is a class member. The variable a is declared as a parsable variable, and hence it is automatically a class member variable. The declaration of j occurs in the scope enclosed by the if statement; as this is not the top-level scope, j is not a class member. The following declaration of i is acceptable; the original one is hidden within that scope. Finally, the declaration of the variable a as a non-parsable would hide the parsable version. As parsable variables do not obey scoping rules, this is not allowed (hiding parsable variables of a base class, however, is allowed). Looking now at the declaration of the class B which contains a variable of type A, it becomes clear which variables are available as class members.

In summary, the scoping rules have the following two special considerations. Parsable variables do not obey scoping rules and are always considered class members. Non-parsable variables obey the standard scoping rules and are considered class members only if they are at the top-level scope of the class.

Note that parameter type variables are considered as having the top-level scope of the class. Also, they are not allowed to hide the object identifier, if any.

### 3.5 Maps

Up to now, we have only considered fixed-length representations, either constant or parametric. A wide variety of representation schemes, however, rely heavily on entropy coding, and in particular Huffman codes . These are variable-length codes (VLCs) which are uniquely decodable (no codeword is the prefix of another). Flavor provides extensive support for variable-length coding through the use of maps. These are declarations of tables in which the correspondence between codewords and values is described.

Figure 9(a) gives a simple example of a map declaration. The map keyword indicates the declaration of a map named A. The declaration also indicates that the map converts from bitstring values to values of type int. The type indication can be a fundamental type, a class type, or an array. Map declarations can only occur in global scope. As a result, an array declaration will have to have a constant size (no non-constant variables are visible at this level). After the map is properly declared, we can define parsable variables that use it by indicating the name of the map where we would put the parse size expression as follows: int(A) i. As we can see the use of variable-length codes is essentially identical to fixed-length variables. All the details are hidden away in the map declaration.

The map contains a series of entries. Each entry starts with a bit string that declares the codeword of the entry followed by the value to be assigned to this codeword. If a complex type is used for the mapped value, then the values have to be enclosed in curly braces. Figure 9(b) shows the definition of a VLC table with a user-defined class as output type. The type of the variable has to be identical to the type returned from the map. For example, using the declaration - YUVblocks(blocks\_per\_component) chroma\_format; \- we can access a particular value of the map using the construct: chroma\_format.Ublocks.

As Huffman codeword lengths tend to get very large when their number increases, it is typical to specify “escape codes,” signifying that the actual value will be subsequently represented using a fixed-length code. To accommodate these as well as more sophisticated constructs, Flavor allows the use of parsable type indications in map values. This means that, using the example in Figure 9(a), we can write the example in Figure 9(c). This indicates that, when the bit string 0b001 is encountered in the bitstream, the actual return value for the map will be obtained by parsing 5 more bits. The parse size for the extension can itself be a map, thus allowing the cascading of maps in sophisticated ways. Although this facility is efficient when parsing, the bitstream generation operation can be costly when complex map structures are designed this way. None of today’s specifications that we are aware of require anything beyond a single escape code.

The translator can check that the VLC table is uniquely decodable, and also generate optimized tables for extremely fast encoding/decoding using our hybrid approach as described in Section 4.6.

### 3.6 Built-In Operators

Operators are built-in functions that are made available to the Flavor programmer in order to facilitate certain frequently appearing data manipulations. These operators are the only functions that are available in the current version of Flavor.

#### 3.6.1 lengthof()

The lengthof() operator is used to obtain the parsed length of a parsable variable. The general syntax is as follows: ‘lengthof(var);’ where var must be a parsable variable of any type that has been previously declared. The result of the operator is treated as an integer.

Since parsable variables can be declared more than once, the operator considers only the last instance of the variable that has been declared (parsed from the bitstream). The following (Figure 10) is an example of the use of the operator.

In Figure 10(b), we declare an one-dimensional array a with five elements. The variable j is set with the length of the last (4-th) element. It is easy to see that the length of this element is going to be 5.

In a declaration such as ‘aligned class A{}’, the bits skipped for alignment are not accounted for by the lengthof() operator. This is true for simple variables as well. These bits, however, are counted for the enclosing class.

#### 3.6.2 isidof()

The isidof() operator is used to check if the value of a varible is among the IDs of a polymorphic class. The general syntax is as follows: ‘isidof(class\_name, var);’ where class\_name is the name of a polymorphic class that has been previously declared, and var is the name of a simple variable. The result of the operator is treated as an integer, and it is 1 if the value of var is among the IDs of class\_name or 0, otherwise.

This operator was introduced to accommodate a coding structure in which the syntax was expressed as: pase as many objects of a particular type as you can from the bitstream. This corresponds to examining the following bits on the bitstream and, if they correspond to an object of the given type, parsing it; otherwise the syntax would continue to the next constrcut. Without this operator, the programmer would have to explicitly construct a switch statement or a series of if-then-else statements, checking against all IDs of the class. This not only would be tiresome, but would also be a source of errors if one of the IDs were not included.

The following is an example of the use of this operator for parsing the above-mentioned constructs.

In Figure 11, we declare an (abstract) class A, with presumably a number of derived classes (not show here). The while loop following the declaration of A examines the next 8 bits of the bitstream. If they correspond to an ID of one of the classes derived from A then the object is parsed; if not, the code continues.

## 4 The Flavor Translator

Designing a language like Flavor would be an interesting but academic exercise, unless it was accompanied by software that can put its power into full use. We have developed a translator that evolved concurrently with the design of the language. When the language specification became stable, the translator was completely rewritten. The most recent release is publicly available for downloading at http://www.sourceforge.net/projects/flavor.

### 4.1 Run-Time API

The translator reads a Flavor source file (.fl) and, depending on the language selection flag, it generates a pair of .h and .cpp files (for C++) or a set of .java files (for Java). In the case of C++, the .h file contains the declarations of all Flavor classes as regular C++ classes and the .cpp file contains the implementations of the corresponding class methods (put() and get()). In the case of Java, each .java file contains the declaration and implementation of a single Flavor class. In both cases, the get() method is responsible for reading a bitstream and loading the class variables with their appropriate values, while the put() method does the reverse. All the members of the classes are declared public, and this allows direct access to desired fields in the bitstream.

The translator makes minimal assumptions about the operating environment for the generated code. For example, it is impossible to anticipate all possible I/O structures that might be needed by applications (network-based, multi-threaded, multiple buffers, etc.). Attempting to provide a universal solution would be futile. Thus, instead of having the translator directly output the required code for bitstream I/O, error reporting, tracing, etc., a run-time library is provided. With this separation, programmers have the flexibility of replacing parts of, or the entire library with their own code. The only requirement is that the customized code provides an identical interface to the one needed by the translator. This interface is defined in a pure virtual class called IBitstream. Deriving from the provided IBitstream class will ensure compatibility with the translator. Additionally, as the source code for the library is included in its entirety, customization can be performed quite easily. The Flavor package also provides information on how to rebuild the library, if needed.

The run-time library includes the Bitstream class that is derived from the IBitstream interface, and provides basic bitstream I/O facilities in terms of reading or writing bits from a binary file. A Bitstream reference is passed as an argument to the get() and put() methods.

If parameter types are used in a class, then they are also required arguments in the get() and put() methods as well. The translator also requires that a function is available to receive calls when expected values are not available or VLC lookups fail. The function name can be selected by the user; a default implementation (flerror) is included in the run-time library.

For efficiency reasons, Flavor arrays are converted to fixed size arrays in the translated code. This is necessary in order to allow developers to access Flavor arrays without needing special techniques. Whenever possible, the translator automatically detects and sets the maximum array size; it can also be set by the user using a command-line option. Finally, the run-time library (and the translator) only allows parse sizes of up to the native integer size of the host processor (except for double values). This enables fast implementation of bitstream I/O operations.

For parsing operations, the only task required by the programmer is to declare an object of the class type at hand, and then call its get() method with an appropriate bitstream. While the same is also true for put() operation, the application developer must also load all class member variables with their appropriate values before the call is made.

### 4.2 Include and Import Directives

In order to simplify the source code organization, Flavor supports %include and %import directives. These are the mechanisms to combine several different source code files into one entity, or to share a given data structure definition across different projects.

#### 4.2.1 Include Directive

The statement - %include "file.fl" \- will include the specified .fl file in the current position and will flag all of its content so that no code is generated. Figure 12(a) displays a .fl file (other.fl) that is included by another .fl file (main.fl). The other.fl file contains the definition of the constant a. The inclusion makes the declaration of the a variable available to the main.fl file. In terms of the generated output, Figure 12(b) outlines the placement of information in different files. In the figure, we see that the main and included files each keep their corresponding implementations. The generated C++ code maintains this partitioning, and makes sure that the main file includes the C++ header file of the included Flavor file.

The %include directive is useful when data structures need to be shared across modules or projects. It is similar in spirit to the use of the C/C++ preprocessor #include statement in the sense that it is used to make general information available at several different places in a program. Its operation, however, is different as Flavor’s %include statement does not involve code generation for the included code. In C/C++, #include is equivalent to copying the included file in the position of the #include statement. This behavior is offered in Flavor by the %import directive.

Similarly, when generating the Java code, only the .java files corresponding to the currently processed Flavor file are generated. The data in the included files are allowed to be used, but they are not generated.

#### 4.2.2 Import Directive

The %import directive behaves similarly to the %include directive, except that full code is generated for the imported file by the translator, and no C++ #include statement is used. This behavior is identical to how a C++ preprocesor #include statement would behave in Flavor.

Let’s consider the example of the previous section, this time with an %import directive rather than an %include one as shown in Figure 13(a). As can be seen from Figure 13(b), the generated code includes the C++ code corresponding to the imported .fl file. Therefore, using the %import directive is exactly the same as just copying the code in the imported .fl file and pasting it in the same location as the %import statement is specified. The translator generates the Java code in the same way.

Note that the Java import statement behaves more like Flavor’s %include statement, in that no code generation takes place for the imported (included) code.

### 4.3 Pragma Statements

Pragma statements are used as a mechanism for setting translator options from inside a Flavor source file. This allows modification of translation parameters (set by the command-line options) without modifying the makefile that builds the user’s program, but more importantly, it allows very fine control on which translation options are applied to each class, or even variable. Almost all command-line options have pragma equivalents. The ones excluded were not considered useful for specification within a source file.

Pragma statements are introduced with the %pragma directive. It can appear wherever a statement or declaration can. It can contain one or more settings, separated by commas, and it cannot span more than one line. After a setting is provided, it will be used for the remainder of the Flavor file, unless overridden by a different pragma setting. In other words, pragma statements do not follow the scope of Flavor code. A pragma that is included in a class will affect not only the class where it is contained, but all classes declared after it. An example is provided in Figure 14.

In this example, we start off setting the generation of both get() and put() methods, enabling tracing and setting the maximum array size to 128 elements. Inside the Example class, we disable the put() method output. This class reads a chunk of data, which is preceded by its size (length, a 10-bit quantity). This means that the largest possible buffer size is 1024 elements. Hence for the data array that immediately follows, we set the array size to 1024, and then switch it back to the default of 128. Finally, at the end of the class we select a different tracing function name; this function is really a method of a class, but this is irrelevant for the translator. Since this directive is used when the get() method code is produced, it will affect the entire class despite the fact that it is declared at its end.

Note that these pragma settings remain in effect even after the end of the Example class.

### 4.4 Verbatim Code

In order to further facilitate integration of Flavor code with C++/Java user code, the translator supports the notion of verbatim code. Using special delimiters, code segments can be inserted in the Flavor source code, and copied verbatim at the correct places in the generated C++/Java file. This allows, for example, the declaration of constructors/destructors, user-specified methods, pointer member variables for C++, etc. Such verbatim code can appear wherever a Flavor statement or declaration is allowed.

The delimiters %{ and %} can be used to introduce code that should go to the class declaration itself (or the global scope). The delimiters %p{ and %p}, and %g{ and %g} can be used to place code at exactly the same position they appear in the put() and get() methods, respectively. Finally, the delimiters %\*{ and %\*} can be used to place code in both put() and get() methods. To place code specific to C++ or Java, .c or .j can be placed before the braces in the delimiters, respectively. For example, a verbatim code to be placed in the get() method of the Java code will be delimited with %g.j{ and %g.j}.

The Flavor package includes several samples on how to integrate user code with Flavor-generated code, including a simple GIF parser. Figure 15 shows a simple example that reads the header of a GIF87a file and prints its values. The print statement which prints the values of the various elements is inserted as verbatim code in the syntax (within %g{ and %g} markers, since the code should go in the get() method). The implementation of the print method for C++ code is declared within %.c{ and %.c}, and for Java, the corresponding implemenation is defined within %.j{ and %.j}. The complete sample code can be found in the Flavor package.

### 4.5 Tracing Code Generation

We also included the option to generate bitstream tracing code within the get() method. This allows one to very quickly examine the contents of a bitstream for development and/or debugging purposes by creating a dump of the bitstream’s content. With this option, and given the syntax of a bitstream described in Flavor, the translator will automatically generate a complete C++/Java program that can verify if a given bitstream complies with that syntax or not. This can be extremely useful for codec development as well as compliance testing.

### 4.6 Map Processing

Map processing is one of the most useful features of Flavor, as hand-coding VLC tables is tedious and error prone. Especially during the development phase of a representation format, when such tables are still under design, full optimization within each design iteration is usually not performed. By using the translator, such optimization is performed at zero cost. Also, note that maps can be used for fixed-length code mappings just by making all codewords have the same length. As a result, one can very easily switch between fixed and variable-length mappings when designing a new representation format.

When processing a map, the translator first checks that it is uniquely decodable, i.e., no codeword is the prefix of another. It then constructs a class declaration for that map, which exposes two methods: getvlc() and putvlc(). These take as arguments a bitstream reference as well as a pointer to the return type of the map. The getvlc() method is reponsible for decoding a map entry and returning the decoded value, while the putvlc() method is responsible for the output of the correct codeword. Note that the defined class does not perform any direct bitstream I/O itself, but uses the services of the Bitstream class instead. This ensures that a user-supplied bitstream I/O library will be seamlessly used for map processing.

According to Fogg’s survey on software and hardware VLC architectures , fast software decoding methods usually exploit a variable-size look-ahead window (multi-bit lookup) with lookup tables. For optimization, the look-ahead size and corresponding tables can be customized for position dependency in the bitstream. For example, for MPEG video, the look-ahead can be selected based on the picture type (I, P, or B).

One of the fastest decoding methods is comprised of one huge lookup table where every codeword represents an index of the table pointing to the corresponding value. However, this costs too much memory. On the other end of the spectrum, one of the most memory efficient algorithms would be of the form of a binary tree. The tree is traversed one bit at a time, and at each stage one examines if a leaf node is reached; if not, the left or right branch is taken for the input bit value of 0 or 1, respectively. Though efficient in memory, this algorithm is extremely slow, requiring N (the bit length of the longest codeword) stages of bitstream input and lookup.

In , we adopted a hybrid approach that maintains the space efficiency of binary tree decoding, and most of the speed associated with lookup tables. In particular, instead of using lookup tables, we use hierarchical, nested switch statements. Each time the read-ahead size is determined by the maximum of a fixed step size and the size of the next shortest code. The fixed step size is used to avoid degeneration of the algorithm into binary tree decoding. The benefit of this approach is that only complete matches require case statements, while all partial matches can be grouped into a single default statement (that, in turn, introduces another switch statement).

With the above-mentioned approach, the space requirement consists of storage of the case values and the comparison code generated by the translator (this code consists of just 2 instructions on typical CISC systems, e.g., a Pentium). While slightly larger than a simple binary tree decoder, this overhead still grows linearly with the number of code entries (rather than exponentially with their length). This is further facilitated by the selection of the step size. When the incremental code size is small, multiple case statements may be assigned to the same codeword, thus increasing the space requirements.

In , we compared the performance of various techniques, including binary tree parsing, fixed step full lookups with different step sizes and our hybrid switch statement approach. In terms of time, our technique is faster than a hierarchical full-lookup approach with identical step sizes. This is because switching consumes little time compared to fixed-step’s function lookups. Furthermore, it is optimized by ordering the case statements in terms of the length of their codeword. As shorter lengths correspond to higher probabilities, this minimizes the average number of comparisons per codeword.

With Flavor, developers can be assured of extremely fast decoding with minimal memory requirement due to the optimized code generation. In addition, the development effort and time in creating software to process VLCs is nearly eliminated.

## 5 Concluding Remarks

Flavor’s design was motivated by our belief that content creation, access, manipulation and distribution will become increasingly important for end-users and developers alike. New media representation forms will continue to be developed, providing richer features and more functionalities for end-users. In order to facilitate this process, it is essential to bring syntactic description on par with modern software development practices and tools. Flavor can provide significant benefits in the area of media representation and multimedia application development at several levels.

First, it can be used as a media representation documenting tool, substituting ad-hoc ways of describing a bitstream’s syntax with a well-defined and concise language. This by itself is a substantial advantage for defining specifications, as a considerable amount of time is spent to ensure that such specifications are unambiguous and bug-free.

Second, a formal media representation language immediately leads to the capability of automatically generating software tools, ranging from bitstream generators and verifiers, as well as a substantial portion of an encoder or decoder.

Third, it allows immediate access to the content by any application developer, for such diverse use as editing, searching, indexing, filtering, etc.

With appropriate translation software, and a bitstream representation written in Flavor, obtaining access to such content is as simple as cutting and pasting the Flavor code from the specification into an ASCII file, and running the translator.

Flavor, however, does not provide facilities to specify how full decoding of data will be performed as it only addresses bitstream syntax description. For example, while the data contained in a GIF file can be fully described by Flavor, obtaining the value of a particular pixel requires the addition of LZW decoding code that must be provided by the programmer. In several instances, such access is not necessary. For example, a number of tools have been developed to do automatic indexing, searching and retrieval of visual content directly in the compressed domain for JPEG and MPEG content (see ). Such tools only require parsing of the coded data so that DCT coefficients are available, but do not require full decoding. Also, new techniques, such as MPEG-7, will provide a wealth of information about the content without the need to decode it. In all these cases, parsing of the compressed information may be the only need for the application at hand.

Finally, Flavor can also be used to redefine the syntax of content in both forward and backward compatible ways. The separation of parsing from the remaining code/decoding operations allows its complete substitution as long as the interface (the semantics of the previously defined parsable variables) remains the same. Old decoding code will simply ignore the new variables, while newly written encoders and decoders will be able to use them. Use of Java in this repect is very useful; its capability to download new class definitions opens the door for such downloadable content descriptions that can accompany the content itself (similar to self-extracting archives). This can eliminate the rigidity of current standards, where even a slight modification of the syntax to accommodate new techniques or functionalities render the content useless in non-flexible but nevertheless compliant decoders.

The authors gratefully acknowledge Olivier Avaro (France Telecom), Carsten Herpel (Thomson Multimedia), and Jean-Claude Dufourd (ENST) for their contributions in the Flavor specification during the development of the MPEG-4 standard. We would also like to acknowledge Yihan Fang, who implemented early versions of the Flavor translator.


format: text

text:
# 1 Abstract

## 1 Abstract

The Ginibre ensemble of complex random Hamiltonian matrices $`H`$ is considered. Each quantum system described by $`H`$ is a dissipative system and the eigenenergies $`Z_i`$ of the Hamiltonian are complex-valued random variables. For generic $`N`$-dimensional Ginibre ensemble analytical formula for distribution of second difference $`\mathrm{\Delta }^1Z_i`$ of complex eigenenergies is presented. The distributions of real and imaginary parts of $`\mathrm{\Delta }^1Z_i`$ and also of its modulus and phase are provided for $`N`$=3. The results are considered in view of Wigner and Dyson’s electrostatic analogy. General law of homogenization of eigenergies for different random matrix ensembles is formulated.

## 2 Introduction

Random Matrix Theory RMT studies quantum Hamiltonian operators $`H`$ for which their matrix elements $`H_{ij}`$ are random variables . There were studied among others the following Gaussian Random Matrix ensembles GRME: orthogonal GOE, unitary GUE, symplectic GSE, as well as circular ensembles: orthogonal COE, unitary CUE, and symplectic CSE. The choice of ensemble is based on quantum symmetries ascribed to $`H`$. It was Eugene Wigner who firstly dealt with eigenenergy level repulsion phenomenon . RMT is applicable now in many branches of physics: nuclear physics (slow neutron resonances, highly excited complex nuclei), condensed phase physics (fine metallic particles, random Ising model \[spin glasses\]), quantum chaos (quantum billiards, quantum dots), disordered mesoscopic systems (transport phenomena). Jean Ginibre considered another example of GRME dropping the assumption of hermiticity of Hamiltonians thus defining generic complex valued $`H`$ . Hence, $`H`$ belong to general linear Lie group GL($`N`$, C), where $`N`$ is dimension and C is complex numbers field. Therefore, the eigenenergies $`Z_i`$ of quantum system ascribed to Ginibre ensemble are complex valued random variables. Jean Ginibre postulated the following joint probability density function of random vector of complex eigenvalues $`Z_1,\mathrm{},Z_N`$ for $`N\times N`$ Hamiltonian matrices :

$`P(z_1,\mathrm{},z_N)=`$ (1)
$`={\displaystyle \underset{j=1}{\overset{N}{}}}{\displaystyle \frac{1}{\pi j!}}{\displaystyle \underset{i<j}{\overset{N}{}}}|z_iz_j|^2\mathrm{exp}({\displaystyle \underset{j=1}{\overset{N}{}}}|z_j|^2),`$
where $`z_i`$ are complex-valued sample points ($`z_i𝐂`$).

We emphasise here Wigner and Dyson’s electrostatic analogy. A Coulomb gas of $`N`$ unit charges moving on complex plane (Gauss’s plane) C is considered. The vectors of positions of charges are $`z_i`$ and potential energy of the system is:

$$U(z_1,\mathrm{},z_N)=\underset{i<j}{}\mathrm{ln}|z_iz_j|+\frac{1}{2}\underset{i}{}|z_i^2|.$$
(2)
If gas is in thermodynamical equilibrium at temperature $`T=\frac{1}{2k_B}`$ ($`\beta =\frac{1}{k_BT}=2`$, $`k_B`$ is Boltzmann’s constant), then probability density function of vectors of positions is $`P(z_1,\mathrm{},z_N)`$ Eq. (1). Therefore, complex eigenenergies $`Z_i`$ of quantum system are analogous to vectors of positions of charges of Coulomb gas. Moreover, complex-valued spacings $`\mathrm{\Delta }^1Z_i`$ of complex eigenenergies of quantum system:

$$\mathrm{\Delta }^1Z_i=Z_{i+1}Z_i,i=1,\mathrm{},(N1),$$
(3)
are analogous to vectors of relative positions of electric charges. Finally, complex-valued second differences $`\mathrm{\Delta }^2Z_i`$ of complex eigenenergies:

$$\mathrm{\Delta }^2Z_i=Z_{i+2}2Z_{i+1}+Z_i,i=1,\mathrm{},(N2),$$
(4)
are analogous to vectors of relative positions of vectors of relative positions of electric charges. The $`\mathrm{\Delta }^2Z_i`$ have their real parts $`\mathrm{Re}\mathrm{\Delta }^2Z_i`$, and imaginary parts $`\mathrm{Im}\mathrm{\Delta }^2Z_i`$, as well as radii (moduli) $`|\mathrm{\Delta }^2Z_i|`$, and main arguments (angles) $`\mathrm{Arg}\mathrm{\Delta }^2Z_i`$. $`\mathrm{\Delta }^2Z_i`$ are extensions of real valued second differences:

$$\mathrm{\Delta }^2E_i=E_{i+2}2E_{i+1}+E_i,i=1,\mathrm{},(N2),$$
(5)
of adjacent ordered increasingly real valued energies $`E_i`$ defined for GOE, GUE, GSE, and Poisson ensemble PE (where Poisson ensemble is composed of uncorrelated randomly distributed eigenenergies) .

## 3 Second Difference Distributions

Let us define following random variables for $`N`$=3 dimensional Ginibre ensemble:

$$Y_1=\mathrm{\Delta }^2Z_1,A_1=\mathrm{Re}Y_1,B_1=\mathrm{Im}Y_1,$$
(6)
$$R_1=|Y_1|,\mathrm{\Phi }_1=\mathrm{Arg}Y_1.$$
(7)
Their distributions for $`N`$=3 dimensional Ginibre ensemble read :

$`f_{Y_1}(y_1)=f_{(A_1,B_1)}(a_1,b_1)=`$ (8)
$`={\displaystyle \frac{1}{576\pi }}[(a_1^2+b_1^2)^2+24]\mathrm{exp}({\displaystyle \frac{1}{6}}(a_1^2+a_2^2)).`$
$$f_{A_1}(a_1)=\frac{\sqrt{6}}{576\sqrt{\pi }}(a_1^4+6a_1^2+51)\mathrm{exp}(\frac{1}{6}a_1^2),$$
(9)
$$f_{B_1}(b_1)=\frac{\sqrt{6}}{576\sqrt{\pi }}(b_1^4+6b_1^2+51)\mathrm{exp}(\frac{1}{6}b_1^2),$$
(10)
$`f_{R_1}(r_1)=`$ (11)
$`\mathrm{\Theta }(r_1){\displaystyle \frac{1}{288}}r_1(r_1^4+24)\mathrm{exp}({\displaystyle \frac{1}{6}}r_1^2),`$
$`f_{\mathrm{\Phi }_1}(\varphi _1)={\displaystyle \frac{1}{2\pi }},\varphi _1[0,2\pi ].`$
For the generic $`N`$-dimensional Ginibre ensemble we study complex-valued random variable of second difference: $`W_1=\mathrm{\Delta }^2Z_1`$. Its distribution is $`P_3(w_1)`$ :

$`P_3(w_1)=`$ (12)
$`=\pi ^3{\displaystyle \underset{j_1=0}{\overset{N1}{}}}{\displaystyle \underset{j_2=0}{\overset{N1}{}}}{\displaystyle \underset{j_3=0}{\overset{N1}{}}}{\displaystyle \frac{1}{j_1!j_2!j_3!}}I_{j_1j_2j_3}(w_1),`$
$`I_{j_1j_2j_3}(w_1)=`$ (13)
$`=2^{2j_2}{\displaystyle \frac{^{j_1+j_2+j_3}}{^{j_1}\lambda _1^{j_2}\lambda _2^{j_3}\lambda _3}}F(w_1,\lambda _1,\lambda _2,\lambda _3)|_{\lambda _i=0},`$
$`F(w_1,\lambda _1,\lambda _2,\lambda _3)=`$ (14)
$`=A(\lambda _1,\lambda _2,\lambda _3)\mathrm{exp}[B(\lambda _1,\lambda _2,\lambda _3)|w_1|^2],`$
$`A(\lambda _1,\lambda _2,\lambda _3)=`$ (15)
$`={\displaystyle \frac{(2\pi )^2}{(\lambda _1+\lambda _2\frac{5}{4})(\lambda _1+\lambda _3\frac{5}{4})(\lambda _11)^2}},`$
$`B(\lambda _1,\lambda _2,\lambda _3)=`$ (16)
$`=(\lambda _11){\displaystyle \frac{2\lambda _1\lambda _2\lambda _3+\frac{1}{2}}{2\lambda _1+\lambda _2+\lambda _3\frac{9}{2}}}.`$
## 4 Conclusions

In order to compare our results for second differences for different ensembles we define dimensionless second differences:

$$C_\beta =\frac{\mathrm{\Delta }^2E_1}{<S_\beta >},$$
(17)
$$X_1=\frac{A_1}{<R_1>},$$
(18)
where $`<S_\beta >`$ are the mean values of spacings for GOE(3) ($`\beta =1`$), for GUE(3) ($`\beta =2`$), for GSE(3) ($`\beta =4`$), for PE ($`\beta =0`$) , and $`<R_1>`$ is mean value of radius $`R_1`$ for $`N`$=3 dimensional Ginibre ensemble .

We formulate homogenization law : Eigenenergies for Gaussian ensembles, for Poisson ensemble, and for Ginibre ensemble tend to be homogeneously distributed. The second differences’ distributions assume global maxima at origin for above ensembles. For Coulomb gas the vectors of relative positions of vectors of relative positions of charges statistically tend to be zero. It can be called stabilisation of structure of system of electric charges.

## 5 Acknowledgements

It is my pleasure to most deeply thank Professor Jakub Zakrzewski for formulating the problem.


text:
# Simulations of unstable gaseous disks and the origin of giant planets

## 1. Introduction

In recent years a large number of extrasolar planets has been discovered via the wobble they induce on their star (Marcy & Butler 1998). Such planets have masses ranging from comparable to Jupiter to ten times larger and have orbits going from nearly circular to very eccentric (Marcy & Butler 2000). When planets have been also detected by means of photometric transits their radius has been determined, indicating that they truly are gas giants (Brown et al. 2001). In the standard core-accretion model giant planets might require longer than $`10^6`$ years to form (Pollack et al. 1996) which would exceed observed disk lifetimes (Haisch, Lada & Lada 2001). An alternative scenario, namely the formation of giant planets by fragmentation of a gravitationally unstable gaseous protoplanetary disk, would occur at least a thousand times faster (Boss 1998). Transient overdensities have been observed in simulations of the disk instability, but whether they can survive and become actual protoplanets has been a puzzle so far (Boss 2001, Pickett et al. 2001). An extremely high resolution is needed to properly represent the self-gravity of the developing overdensities and to prevent them from being artificially sheared apart by the stellar tidal force (Boss 1998,2001). In addition, restrictive boundary conditions can enhance instabilities or suppress already formed overdensities that happen to move out of the computational volume (Pickett et al. 2001). Smoothed particle hydrodynamics (SPH) simulations describe the gaseous medium as a collection of particles and, being spatially adaptive by construction, can follow arbitrarily high densities. Such simulations can thus properly follow the overdensities once a sufficiently large number of particles is employed and numerical issues like artificial fragmentation are overcome (see Nelson 1998 and these proceedings; Bate & Burkert 1997). Here we present new 3D SPH simulations of unprecedented resolution showing for the first time that long-lived, self-gravitating protoplanets arise as a result of fragmentation in disks with masses comparable to those inferred for the protosolar nebula.

## 2. Initial Conditions and Simulations

Our protoplanetary disk models closely follow those of Boss (2001) who used a different numerical technique, namely a grid code with fixed boundaries. We start from smooth, axisymmetric self-gravitating disks which extend from 4 to 20 AU and are in near-keplerian rotation around a solar mass star represented by a point mass. The stellar potential is exactly keplerian at 2.5 AU and it is softened on smaller scales to speed up the computation. The gravitational softening of the gas particles is chosen small enough to resolve gravity at least as well as the hydrodynamical forces up to the onset of the nonlinear stage (the resolution of the hydrodynamical forces is variable in SPH and increases as the local density increases). The simulations were performed with GASOLINE, a highly parallel N-Body/SPH code widely used in cosmology/galaxy formation. Thanks to the multistepping capabilities of the code which allow to follow a huge dynamic range we adopted free boundaries. The disks have a minimum Toomre Q parameter of either $`1.4`$ or $`1.75`$, reached at the outer disk boundary, and masses of, respectively, $`0.1`$ and $`0.08M_{}`$.

The initial temperature follows a power law profile (temperatures are $`50`$ K at $`R>10`$ AU and reach $`650`$ K at 4 AU) predicted by detailed calculations of thermal balance between the central star, the disk and the protostellar cloud (Boss 1998). Recent models of protoplanetary disks yield outer disk temperatures at least as low as those used here (D’Alessio, Calvet & Hartmann 2001). As for their thermodynamical evolution, disks are evolved either maintaining the initial temperature profile (a lagrangian locally isothermal approximation, i.e. the temperature of a given bucket of particles is kept constant) or allowing them to keep the heating resulting from adiabatic compression and/or shocks once sufficiently strong overdensities appear. The second type of simulations accounts for the fact that the gas would behave nearly adiabatically once its mean density grows beyond a certain value (Boss 2001)- it will not be able to radiate away its internal energy as efficiently as assumed with the locally isothermal approximation. We performed simulations with as many as 1 million gas particles as well as lower resolution simulations. We found numerical results to nearly converge with at least 200.000 particles; the latter faster computations were used to study disks for longer timescales.

## 3. Results

After $`150`$ years (5 orbital times at the reference radius of 10 AU) all disks develop trailing spiral arms and local overdensities at $`R>10`$ AU. While in disks with $`Q1.75`$ the spiral pattern grows and then reaches a weaker, near-stationary pattern up to $`500`$ yr, in disks with $`Q1.4`$ fragmentation occurs along the spiral arms, and several clumps appear. Subsequently other clumps form down to $`78`$ AU (inside this radius the disk is too and non-axisymmetric instabilities are suppressed). Once formed, these clumps contract reaching densities as high as $`10^5`$ times the initial local value on their free-fall timescale (tens of days); their collapse then is nearly halted as the interparticle separation becomes much smaller than the gravitational softening and the resolution limit of our calculation is reached - in this regime gravity is artificially weaker than pressure forces (Bate & Burkert 1997).

These highly dense clumps are self-gravitating and easily resist stellar tides (Figure 1). Clump formation and collapse is basically independent on how the disk evolves thermodynamically once regions with densities at least ten times higher than the initial local density have appeared. Individual clumps can collide and merge with other clumps. As shown in Figure 2,after 350 years protoplanets exhibit a mass function qualitatively close to that of observed extrasolar planets (e.g. Marcy & Butler 2000) - planets smaller than Jupiter likely do not form because of resolution limits. Once clumps collapse to very high densities it becomes increasingly difficult to follow the disk evolution as computational timesteps becomes very small. We thus resort to the simulations with 200.000 particles (which also have particle softening increased by a factor of three for numerical consistency - see Dehnen 2002). In these runs a smaller number of clumps forms due to the lower resolution but their dynamical evolution is followed for up to nearly 103 years. At the end of the simulations only three protoplanets remain with masses between 2 and 6 $`M_{Jup}`$ and these are on orbits ranging from nearly circular to an eccentricity of about 0.3, between 3 and 15 AU (Figure 1). This final stage is reached several orbital times before the simulations are ended and therefore we believe it is fairly representative of the dynamical evolution of protoplanets formed in this instability model. Of course, both orbital migration (Bryden et al. 1999) and secular dynamical interactions between the protoplanets (Terquem & Papaloizou 2002) can still occur on timescales much longer than those explored here and might change the orbits.

## 4. Conclusions

Our SPH simulations answer for the first time one of the fundamental question regarding the instability model; can overdensities survive and turn into tidally stable, self-gravitating protoplanets? We find that they can once a sufficiently high resolution is used and no restrictions are imposed on the dynamical evolution of the disk. Nearly all the clumps at some point in their evolution reach distances from the central star that are either larger or smaller than the initial disk boundaries and would have been lost in a simulation that preserves the latter. We also show that systems of giant planets with masses and orbital eccentricities close to those of observed extrasolar planets naturally arise. Therefore, we conclude that the gravitational instability picture is a viable model for giant planet formation. Whether keeping the disk locally isothermal until the first strong overdensities appear is physically motivated needs to be explored in more detail. For this to happen radiative cooling must be very efficient at dissipating the heat resulting from compressions and shocks occurring during the earlier stages (Pickett et al. 2001). In addition, future work will also be directed to find a more realistic setup of the initial conditions using a disk actually grown from the protostellar cloud. This will allow the investigation of how likely is a situation in which a disk has $`Q_{min}1.4`$; indeed mild spiral instabilities at an earlier stage, when the disk is lighter or hotter, could drive it rapidly towards a much higher $`Q`$ (Laughlin & Roczyska 1994). However, the model with $`Q_{min}1.75`$ still has a $`Q1.7`$ after 350 years, suggesting that weak spiral instabilities are not very efficient in redistributing mass and stabilizing the disk.

## References

Bate, M., & Burkert, A. 1997, MNRAS, 288, 1060

Boss, A.P. 1998, ApJ, 503, 923

Boss, A.P. 2001, ApJ, 563, 367

Bryden, G., Chen, X., Lin, D.N.C, Nelson, R.P., Papaloizou, J.C.B, 1999, ApJ, 514,344

Brown, T. M., Charbonneau, D., Gilliland, R. L., Noyes, R. W,& Burrows, A. 2001, ApJ, 552, 699

D’Alessio, P., Calvet, N., Hartmann, L., 2001, ApJ, 553, 321

Dehnen, W. 2001, MNRAS, 324, 273

Haisch, K.E., Jr., Lada, E.A. & Lada, C.J. 2001, ApJ, 553, L153

Laughlin, G. & Rozyczka, M. 1996, ApJ, 456, 279

Marcy, G. W. & Butler, R. P. 1998, ARAA, 36, 57

Marcy, G. W. & Butler, R. P. 2000, PASP, 112, 137

Nelson, A.F., Benz, W., Fred, A.C. & Arnett, D. 1998, ApJ, 502, 342

Pickett, B.K., Durisen, R.H., Cassen, P. & Mejia, C. 2000, ApJ, 540, L95

Pollack, J. B. et al. 1996, Icarus, 124, 62

Terquem, C., & Papaloizou, J.C.B. 2002, MNRAS, 332, L39