More generally, the invention lies within the context of multime- dia.

A set of digital broadcast data recorded on a direct-access re- cording medium (CD, DVD, hard disk) generally comprises, in addition to the broadcast information, navigation information, making it possible to ob- tain at least one position from the broadcast information recorded. This navigation information makes it possible to identify at least some of the ac- cess units forming the broadcast stream and makes it possible to have ac- cess individually to each group of access units or to groups of access units on the storage unit in order to read them off. These navigation data may be transmitted with the broadcast streams or may have been produced locally in the system by analyzing the broadcast stream.

The set of digital broadcast data consisting of the broadcast stream and of the navigation information may be a data structure grouping together access units, and allows random access to each access unit or to groups of access units. This structure is called Enriched Multimedia Struc- ture in the case of the present application.

By"broadcast information"is understood any information in- tended to be distributed in the course of time from a recording medium, ei- ther directly to a bradcast apparatus (television set, audio system, etc.) or to a transmission channel. The broadcast information relates, for example but not exclusively, to video and/or audio signals, but may also relate to signals of another nature. In a general way"object"designates an element or a group of elements constituting the broadcast stream."Direct-access recording medium"designates any information medium allowing direct posi- tioning in read mode, and possibly in write mode, either at any position of the medium or at certain access positions.

In practice, in the case of an audiovisual stream compressed, for example, according to an MPEG standard (acronym for"Motion Picture Ex- pert Group") such as MPEG-2, packets of the elementary-stream type are

recorded, known as PES ("Packetized Elementary Streams") packets, or packets of the transport-stream or TS type on a hard disk or HDD ("Hard Disk Drive"). In this case, an object could designate an MPEG image, or a group of MPEG images, or a PES packet or an MPEG audio frame, or a set of multiplexed TS packets.

In systems in which the broadcast stream is stored in a storage device, possibly being a hard disk, for example, in a digital video decoder, before being read off and sent to an MPEG decoder, the user wishes to have the possibility of using special presentation modes. The special pres- entation modes (or"trick modes") may consist particularly of replay modes in fast forward or fast reverse, slow-motion or pause on images.

The presentation, in the reverse order, of a video sequence en- coded to the MPEG format is a difficult problem. This is because, according to the MPEG format, the access units constituting the MPEG video stream are coded by reference to the previously transmitted object. In fact, the ac- cess units are transmitted in the order of their decoding in order to be dis- played finally in a different order.

The Enriched Multimedia Structure allows analysis of the broad- cast multimedia content which it describes and its processing especially in order to implement special presentation modes.

According to known systems, an appropriate processing of an EMS (Enriched Multimedia Structure) containing video makes it possible to present its content the right way round or backwards, at an accelerated or slowed speed. Thus all the display modes conventionally available on video recorders are implemented.

A study into this type of processing has shown that the accesses to the broadcast data within these trick modes may have the following prop- erties: - the access units are read non-continuously : - they are not all read - they are not read in a precise order.

- certain access units are read several times in a limited period, and at closely spaced instants.

The conventional methods for access and forwarding of a stream employ systems for pseudo-continuous reading of the storage medium, us-

ing a circularly managed buffer memory. These methods prove to be poorly adapted to the trick modes described above since : - continuous reading causes more than just the necessary ob- jects to be read, - with the direction of reading of the stream possibly not being constant, there are embarrassing discontinuities relating to the circularity of the buffer and to its non-continuous filling, - if it is desired to keep one access unit in the circular buffer longer than the others, it is not possible to free from the buffer the access units which are unused but loaded later.

The present invention therefore proposes a device making it possible to overcome the drawbacks mentioned above, by accessing the stream image by image in order to avoid wasting memory, while optimizing accesses to the recording medium.

To that end, the present invention proposes a device for manag- ing access to a recording medium including a set of digital broadcast data, the said set comprising broadcast information and navigation information, characterized in that it includes: - a cache memory for temporarily storing broadcast information read from the recording medium and a data structure including at least data included in the navigation information associated with this broadcast infor- mation, - a means of managing broadcast information present in the cache memory, in order to erase broadcast information and its associated data structure, present in the cache memory, and in order to read digital broadcast data from the recording medium so as to write the corresponding broadcast information and its associated data structure into the said cache memory.

The device is called an Images Cache.

The Images Cache has to serve its clients by making available to them, in memory, the objects which they require. The Images Cache is therefore responsible for managing the cache memory which is dedicated to it, for loading new objects into it from the recording medium and for delet- ing the obsolete objects from it.

The cache memory is a memory area substantially smaller in size than the size of the recording medium but with an access mode and times which are typical of the memory, in this instance faster than the re- cording medium.

The cache memory of the Images Cache is a memory area in which the broadcast information is temporarily stored. This memory area may simply be a partition of the shared memory of the system. The broad- cast information is preferably digital data coming from a recording medium and intended for a broadcast apparatus or a transmission channel. These broadcast data are generally coded according to a standard such as MPEG-2 and represent access units or groups of access units.

The management means may simply be software run on the computing unit available in the system and shared. It could also be imple- mented as hardware by an ASIC cell (an acronym for"Application Specific Integrated Circuit"). This management means decides on the reading of new objects from the recording medium and on the deletion of old objects already present in the memory of the cache, so as to ensure that the ob- jects which are requested from it are present in cache memory.

The data structure serving for the management of the Image Cache lists at least the identifiers of the broadcast information stored in memory and the parameters specific to its storage (address and size, for example). It makes it possible to know which are the broadcast data pre- sent in the cache and to have access to these data in order to read them.

According to one particular characteristic, the data structure re- lating to the broadcast information includes at least data taken from among the type, the time-based reference and the index of the broadcast informa- tion. The data structure therefore contains data allowing the image cache to manage the images which it contains in an effective way.

These parameters allow advantageous management of the broadcast data present in the cache. This is because, when a new object is necessary for the decoding, the management means of the cache memory has to replace the broadcast data by data read from the recording medium corresponding to the object requested by the decoder.

In one preferred embodiment, the broadcast information is pref- erably audio and/or video and is intended for trick modes.

The invention is particularly advantageous in this case by com- parison with the known techniques, especially in the case of reading in re- verse play mode where the use of circular buffers does not make it possible to extract the access units in a different order from that in which they were input. Moreover, the data structure associated with the broadcast informa- tion makes it possible to load the desired image.

According to another characteristic, the management means, when it receives a broadcast information demand request, erases broad- cast information and its associated data structure, which are present in the cache memory, and reads digital broadcast data from the recording me- dium on the basis of the associated navigation information or of information present in the associated data structure and of trick modes.

Thus, when a new object is necessary for the decoding, the management means of the cache memory replaces broadcast data by data read from the recording medium corresponding to the object requested by the decoder.

According to a first embodiment, the management means in- cludes a means of weighting broadcast data, the said weighting means weighting the broadcast information on the basis of the information on the data structure associated with the broadcast information to be weighted and/or on the basis of the trick modes.

The weighting means uses a weighting rule such that the broad- cast data for which the deletion and the subsequent reloading are only slightly or not at all are erased more rapidly than the others.

The management means can thus optimally determine the obso- lescence of the objects present in the cache memory so as to delete them and free the memory spaces which will be able to receive the new objects requested by the client, while guaranteeing that a minimum number of ob- jects will be loaded from the storage unit.

For example, in the case of an MPEG-2 video stream, the ob- jects are images, the image to be deleted from the cache will be determined on the basis of the index of the image requested and of the direction of the presentation. In forward play mode, it is the image which has the lowest in- dex which will be deleted from the cache. In reverse play mode, it is the im- age which has the largest index which will be deleted.

However, because of the fragmentation of the cache memory, it may happen that the deletion of a single object is not sufficient to free enough space in the cache for the new object to be loaded.

It may then be beneficial to delete successively from the cache memory the broadcast data stored at an address contiguous with the broadcast data which have previously been erased. This second iterative phase of memory freeing makes it possible to ensure that these new dele- tions of objects actually increase the size of a free monolithic memory area.

It is then possible to assess that a minimum number of objects are thus de- leted from the cache in order to free the required memory space.

These presentation modes are in fact currently used in numer- ous video systems.

Correspondingly, the invention relates to a method of access to a recording medium including a set of digital broadcast data, the said set comprising broadcast information and navigation information, preferably audio and/or video, the said broadcast data possibly being intended for various trick modes.

According to the invention, - broadcast information read from the recording medium and a data structure associated with the said broadcast information are stored temporarily in a cache memory, - broadcast information present in the cache memory is man- aged on the basis of the predetermined special presentation mode by eras- ing broadcast information present in the cache memory, and by reading digital broadcast data from the recording medium so as to write the corre- sponding broadcast information and its associated data structure into the said cache memory.

The invention also relates to a video-decoding device including a device for management of access to a recording medium as described above.

The invention also relates to a television receiver including a de- vice for managing access to a recording medium as described above.

The advantages cited previously for the device apply equally to the method according to the invention, to the video-decoding device as well as to the television receiver.

The invention will be better understood, and other features and advantages will become apparent, on reading the description of the em- bodiment examples which will follow, given by way of non-limiting exam- ples, by reference to the attached drawings, among which: - Figure 1 represents a diagram of a television decoder, - Figure 2 represents a diagram of the software model of a part of the device of Figure 1 and implemented for the trick modes, - Figure 3 represents an example of enriched multimedia struc- ture according to the present embodiment example, - Figure 4 represents the data structure associated with the broadcast information stored in the cache memory, - Figure 5 represents a flow chart for loading of a new image into the cache memory, implemented by the management means.

The digital television-receiver decoder of Figure 1 comprises an error-corrector circuit 2 fed by a tuner and an analog/digital converter (which are not represented). The corrected digital signal is sent to a trans- port-stream demultiplexer filter 4. This demultiplexer filter 4 is connected to a central communications bus 3 of the receiver 1. Its role is to select the transport-stream packets in the incoming new data stream and to send them to the various applications of the receiver. To that end, it comprises filters programmed by a microprocessor 11.

In order to record the MPEG streams, the receiver comprises a hard disk 8 linked to the bus 3 by an interface 7, for example an EIDE inter- face. A unified memory 6 is shared by all the processes of the receiver.

This memory comprises, in particular, a memory area allocated to the im- ages cache.

In order to decode a stream, the receiver 1 also comprises audio and video decoders 12 and 13 respectively, connected to a central bus 3. A second transport-demultiplexer filter 9 is capable of filtering the audio and video components of a recorded transport stream originating from the EIDE interface and of transferring them to the memory 6 or to the decoders 12 and 13. Depending on the recording mode, the layer of the transport stream may or may not previously have been taken off.

For this description, the navigation information comprises, for each video access unit stored on the disk, and in the order of recording, the

image type (I, P or B), its time-based reference, the location of the image in question, and also links and details on the groups of images.

A navigation information structure example is described in the European Patent Application entitled"Method and device for decoding a digital video stream in a digital video system using dummy header insertion" under filing number 00400941.1 filed in the name of THOMSON Multimedia on 5 April 2000.

Figure 2 is a diagram of the software model of the receiver 1. It comprises the following elements: - the presentation supervisor (14).

This software module has the role of the general control of the decoding method. Depending on the method of presentation (for- ward/reverse, slow/fast), this module specifies which image should be for- warded, decoded or displayed.

For example, if the presentation mode is fast reverse reproduc- tion with a normal speed multiplied by X, this module determines which im- age is to be displayed, the type of image (I, B, P) and, in the case of a P-or B-type image, the other images which should be decoded beforehand. This method is executed recursively.

The presentation supervisor accesses the navigation information by way of the navigation-information access manager.

Based on the recursive decoding algorithm, the presentation su- pervisor schdules the images cache to supply it with the memory ad- dresses 6 of the video-access units which it wishes to transfer to the MPEG video decoder 13.

- the navigation-information access manager (19).

The presentation supervisor needs navigation information on the recorded streams. This information is stored on the hard disk 8. The navigation-information Access Manager has the role of collecting the information from the hard disk 8 and of supplying it to the presentation supervisor as and when the latter requests it.

- the image-cache manager (20).

Each image which is to be decoded (either in order to be dis- played or not displayed later on) has to be forwarded to the MPEG video decoder 13 after having been temporarily loaded into memory 6. All the in-

formation necessary for accessing the compressed content is supplied in the navigation information. The image cache has the role, moreover, of transferring the data of the image identified by the presentation supervisor from the hard disk into the memory 6 if necessary. For each image having to be decoded, the images cache is called on by the presentation supervi- sor to supply the parameters necessary for transfer of the image from the memory 6 to the decoder 13, and especially the address of the image in memory and its size.

The manager of the image cache 20 implements the flow chart of Figure 5. When it has to erase data from the cache memory (6) in order to free memory space for storing a new image, it takes into account the parameters of the associated data structure as well as the current special presentation mode requested, and weights these various parameters in or- der to determine the image to be deleted.

- The video decoding supervisor (15) The video decoder informs the video decoding supervisor when it receives and identifies a new video access unit. The video decoding su- pervisor has previously received, by way of a queue originating from the presentation supervisor, a complete command scheduling and specifying the decoding and/or the display of this precise image. Based on this com- mand, the video decoding supervisor programs the decoding of this new image detected and, if the image is to be displayed, announces to the video display manager that this image has to be displayed and how this should be done (order of the interlaced frames).

The MPEG video decoding API (Application Programmable Inter- face) (16) allows certain types of checks and operations relating to the de- coding and any displaying of individual images. In particular, the API can receive the order to decode an individual image and to display it subse- quently at a given time and for a certain number of image intervals, or not to display it at all.

The presentation supervisor requests forwarding of a new image when necessary, and waits until the forwarding is terminated before send- ing another request. The completion of the forwarding is signalled to it by the manager of the images cache.

Figure 3 represents the enriched multimedia structure. The en- riched multimedia structure consists of the digital broadcast stream 60 and of navigation information associated with the various access units 61,62, 63,64 making up this broadcast stream 60.

The digital broadcast stream 60 consists of access units 61,62, 63,64. Navigation information is associated with each access unit. The navigation information 71 and 81,72 and 82,73 and 83,74 and 84 is asso- ciated respectively with the access units 61,62,63,64. Among this naviga- tion information there is the size of the access unit, the address of the ac- cess unit and other parameters. The items of navigation information from one access unit to another are also related to each other. In fact, it is desir- able for certain types of streams, such as MPEG 2 for example, to know what the preceding or following image is. This information is stored in rela- tionship tables 81,82,83,84 associated respectively with the access units 61,62,63 and 64 and forming part of their respective enriched multimedia structures.

Figure 4 represents the data structure (50) associated with the broadcast information stored in the cache memory (6).

Each data structure 50 includes two types of information, on the one hand information 52 on the characteristics specific to the image itself and information 51 on the address of the image in the cache memory and its size, the address and the size being information which is necessary for managing any cache memory.

The information present in the field 52 allows advantageous management of the cache memory. This information is, for example, the type of the image, the time-based reference of the image and the index of the image.

In Figure 5, at stage E1, the presentation supervisor makes a re- quest for a new image. The image cache then, at stage E2, runs through its N rows of cache. During the test of stage E3, if the required image is in the cache, stage E10 is entered, otherwise stage E4 is entered.

At stage E4, it is decided which image from the cache is to be deleted in order to place the required new image in it. The choice of the im- age to be deleted takes account of the navigation information associated with the said image, of the trick modes and of the data structure associated

with the said image. These criteria are weighted so as to define the image to be erased.

At stage E5, when the image to be deleted has been determined, the memory area corresponding to this image is deallocated.

At stage E6, the navigation information of the image required is copied into the data structure of the cache in place of the navigation infor- mation of the deleted image. This information especially gives the size of the required image.

At stage E7, a test is done to discover whether the space deallo- cated in the course of stage E5 is sufficient to store the required image. If the size of the deallocated space is smaller than the size of the required image, then, at stage E8, an additional image is deleted, this image pref- erably being stored in memory in an area contiguous with the previously deleted image.

Otherwise, if the deallocated memory space is sufficient to store the required image, stage E9 is entered during which the required image is loaded from the hard disk to the image cache.

Next, stage E10 is entered, in which it is then possible to give the presentation supervisor the details of the coordinates of the image in mem- ory 6 so that it can transfer it to the video decoder.

An example routing of the data in the television decoder of Fig- ure 1 will now be described, in the case in which reverse play mode is taken as a special presentation mode.

Let us consider that the size of the cache is fixed at 4, and that the cache contains the following 4 images: - row A, the image with index value 1234, intra image 0, - row B, the image with index value 1235, predictive image 3, - row C, the image with index value 1238, predictive image 6, - row D, the image with index value 1240, predictive bidirectional image 5. the image index 1240 being the last image which has been used and re- quested by the supervisor of the trick modes 14.

The supervisor now requests the image B4 (predictive bidirec- tional image 4) which precedes the bidirectional image 5. This request from the supervisor consists in forwarding, to the image cache, a reference in

memory to the descriptor of the image which it wants. The image cache finds, in the descriptor of the image, the index of the desired image which is 1239, and it will be able to compare this index with the indices of the im- ages which are already in the cache, the indices being stored in memory in the data structure. The scanning of the data structure therefore gives the result that the image 1239 is not present in the cache. It will therefore be necessary to load the image 1239 into the cache, but in order to do that it is necessary to free some space.

Let us assume, as an example, that the weighting means uses the index of the image in order to perform the weighting. In reverse play mode, the image which has the largest index has to be deleted, i. e. here the image with index 1240.

The data associated with the image of row D in the data struc- ture are the index 1240, the type, bidirectional, the number 5 of the image (the time-based reference) in the GOP, the size of the image (11356) and the memory address of the compressed data of the image. Firstly, there- fore, the memory area which was used for the image with index 1240 is de- allocated, giving the memory manager the address of this area.

The data associated with cache row D are then updated on the basis of the descriptor of the new image in the navigation information.

These data are the index, 1239, the type, B, the time-based reference, 4, the size 11356 bytes and a non-meaningful address, for example 0x00000, this address being filled in when the data are written into the cache.

A memory area has to be reserved in order to be able to store the compressed data of this image in it. The memory manager is then called on to allocate 11536 bytes. If this allocation is successful, the man- ager returns the address of the allocated region OxAF000800, for example.

This address is then written into the data structure to replace the initial, non-meaningful address.

If the memory space freed by the deletion of the image from the cache row D, with index 1240, had not been sufficient, it would have been necessary to delete an additional image from the cache in order to free more memory. It would then have been possible to search for the cache row or rows which use memory areas adjacent to the area which has just been deallocated and to delete this row then reattempt an allocation.

The compressed data of the image are then loaded from the hard disk (recording medium) into the cache memory, in the previously allo- cated area. In order to access the image in the digital file in the course of reading, the position of the first bite of this image in the file is used, which is supplied by the navigation information. This position, the size of the image and the address where it is to be loaded are forwarded to the file manager which transfers the data from the hard disk into the memory. Once this transfer has been terminated, it is possible to resend the digital data from the cache memory to the MPEG video decoder.

The images cache is then ready to process a new request. This request is, logically, a request for the predictive image 3, that is to say the image with index 1235 present at cache row B. With this image being al- ready in the cache, the cache forwards it directly to the MPEG video de- coder, and no reading of data on the hard disk is necessary.

The images are loaded only once into the cache, and perform- ance is therefore enhanced. The operations within the video decoding de- vice are paralleled. For example, when the cache is reading broadcast in- formation from the disk, the preceding image is transferred to the MPEG video decoder by using, for example, a transfer of DMA type driven by the processor 11. During this time, the decoder decodes the preceding image and the display displays yet another preceding image.