United States Patent [191
`Ran
`
`[54] VIDEO CODING USING SEGMENTED
`FRAME AND RETRANSMISSION TO
`OVERCOME CHANNEL ERRORS
`
`[75]
`
`[73]
`
`[21]
`[22]
`[51]
`[52]
`[58]
`
`Inventor:
`
`Xiaonong Ran. Cupeitino. Calif.
`
`Assignee: National Semiconductor Corporation.
`Santa Clara. Calif.
`
`Appl. No.: 522,688
`Filed:
`Sep. 1, 1995
`
`Int. Cl? ..................................................... .. 601D 1/16
`.. ass/200.77; 395/181
`Field of Search ........................ .. 364/514 R. 715.02;
`371/32. 34. 37.1. 37.7. 38.1. 39.1. 40.2.
`41. 48. 55; 395/181. 182.04. 182.16. 182.19.
`185.01. 185.05.200.77; 382/309; 341/94
`
`[56]
`
`References Cited
`
`U.S. PATENT DOCUNIENTS
`
`Re. 31,182
`4,829,524
`5,105,423
`5,481 ,566
`
`3/1983 Crager et al. ............................. .. 178/3
`
`5/1989 Yoshida . . . . . . . . . . . .
`
`. . . .. 371/32
`
`371/55
`4/1992 Tanaka et al.
`1/1996 Kulesa .................................. .. 375/259
`
`OT HER PUBLICATIONS
`
`Goodman. D. et al.. “Combined Source and Channel Coding
`for Variable-Bit-Rate Speech Transmission”. 62 The Bell
`System Technical Journal 2017-2035 (1983).
`
`US005768533A
`Patent Number:
`[11]
`[45] Date of Patent:
`
`5,768,533
`Jun. 16, 1998
`
`Primary Examiner-James P. Trarnmell
`Assistant Examiner-Thomas Peeso
`Attorney Agent; or Firm-Skjerven. MOlTill. MacPherson.
`Franklin & Friel; Edward C. Kwok; David T. Millers
`
`[57]
`
`ABSTRACT
`
`A communication system and protocol uses retransmission
`techniques for video transmission on mobile/Wireless chan
`nels. The system partitions frames of a moving image into
`frame segments. and combines a sequence of frame seg
`ments to form a sub-sequence of the moving image. The
`sub-sequences are treated as separate images which are
`separately encoded and transmitted to a receiver and then are
`combined to reassemble the moving image. A sender trans
`mits to the receiver data packets. each data packet repre
`senting all or part of a digital code for a frame segment. The
`receiver requests retransmission of data packets containing
`detectable errors. indicates in a status buifer which digital
`codes have been received and whether the digital codes are
`intra or inter codes. and displays a frame only after all
`required data packets have been received without detectable
`errors. The segmented frames limit occasional failures to
`accurately retransmit data to individual sub-sequences. so
`that the failure to accurately transmit data is compensated
`for by subsequent transmission an intra coded digital code
`for a frame segment.
`
`21 Claims, 2 Drawing Sheets
`
`J‘lk _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ j
`
`SENDER
`VIDEO
`SOURCE
`
`155
`
`e'mfgg?
`/
`160
`
`‘I
`\
`1
`
`‘
`‘
`l
`|
`l
`1
`|
`
`175\
`BUFFER
`CONTROLLER
`‘_|
`TRANSMISS/ION
`BUFFER
`‘
`185
`‘I
`RETRANs. *
`CONTROLLER
`
`1 B0
`
`I
`|
`1
`I
`1
`I
`|
`|
`:
`I
`
`170
`"
`\
`VlDEO ENCODEH
`1‘
`I
`
`165\
`
`Q L190
`I
`HETRANS.‘
`STATUS COUNTERS
`FIFO
`
`L _ — q — — — _ — w - ? a _ — — _ g — _ — _ _ 145A/ 1
`
`145
`
`100
`
`CHANNEL
`_/145B
`
`_ _\ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - _ _ j
`
`l
`
`l l
`
`1
`l
`'
`I
`l
`
`RECE'VEH
`
`com
`/
`105
`
`VbDEEIgIER
`
`STATUS BUFFER
`
`115/
`
`'
`
`I
`
`REQUEST
`
`CoNTRQLLER
`
`125
`
`.
`
`1
`
`I
`
`I
`I
`
`OUTPUT
`BUFFER f ‘"050
`110/
`120/
`
`EH 1
`DECOD
`
`REcEwmG
`i
`BUFFER
`130/
`
`'
`I
`
`Apple Inc. v. Parthenon
`Ex. 1009 / Page 1 of 10
`
`

`

`U.S. Patent
`
`Jun. 16, 1998
`
`Sheet 1 of 2
`
`5,768,533
`
`__________
`
`_I
`
`.1
`
`Eozmm_Iuuaus14/3.. Euzsm89>”mt
`
`EjoEzoo_momaow
`
`
`
`_______
`
`oz_>_mom¢
`
`$u_u5m
`
`
`mm._._oE.zooIIIIIIIII
`BmsommEumamm2.<5
`
`IIIIIIIII
`nnnunnnnu
`
`mm:._oE.zooE:mmfizaoomafia
`
`.mz<Em_m.mz<—mm.“E=-------
`
`zo_mw_saz<EEooozm89>5%.
`mmmwsm.12:
`
`m:
`
`0:me
`
`Ex. 1009 / Page 2 of 10
`
`

`

`U.S. Patent
`
`Jun. 16, 1993
`
`Sheet 2 of 2
`
`5,768,533
`
`_______x__._f.___.
`
`Ex. 1009 / Page 3 of 10
`
`

`

`5,768,533
`
`1
`VIDEO CODING USING SEGMENTED
`FRAMES AND RETRANSMISSION TO
`OVERCOME CHANNEL ERRORS
`
`BACKGROUND OF THE INVENTION
`
`2
`included error correction coding for video which is similar
`to the error correction coding used in mobile/wireless tele
`phones. However. errors in video data which cannot be
`corrected by algebraic error correction result in video dis
`played with ?awed areas containing incorrect colors and/or
`intensities. These ?awed areas can be very noticeable and
`distracting. Additionally many of the most e?icient video
`compression processes use encoding commonly referred to
`as “inter” coding. Inter coding encodes changes between
`successive frames of a moving image. and the receiver adds
`the inter coded data to data from a previous frame to
`determine a current frame of the moving image.
`Unfortunately. with inter coding. new inter coded data builds
`new frames on frames containing flaws. and the receiver
`may preserve and repeat ?aws caused by an uncorrectable
`error. Furthm'. uncorrectable errors can accumulate from
`several frames. resulting in poor image quality. Avoiding
`inter coding can prevent accumulation of ?aws but typically
`decreases compression e?iciency which decreases maxi
`mum frame rate and/or image quality. Accordingly. a system
`is needed which eliminates the ?awed areas displayed by
`videophones and. permits use of inter coding.
`
`SUMMARY OF THE INVENTION
`
`In accordance with the invention. a communication sys
`tem such as a videophone system uses retransmission to
`correct channel errors in signals representing a moving
`image. Each frame of the moving image is displayed only
`after all necessary data for the frame has been received
`without errors that are detectable by a receiver. Accordingly.
`each frame of the moving image is displayed without ?aws
`that commonly appear in systems using algebraic error
`correction.
`In one embodiment of the invention. a moving image is
`spatially partitioned into sub-sequences which are sequences
`of frames segments. each frame segment being part of a
`frame of the moving image. Sub-sequences are encoded
`separately so that channel errors in one sub-sequence do not
`affect other sub-sequences. Typically. a sender inter codes
`frame segments for the sub-sequences and transmits digital
`codes representing the frame segments to a receiver. The
`receiver requests retransmission when an error is detected in
`a digital code representing a frame segment. However. if
`retransmission fails to provide error-free data for the frame
`segment in time for decoding. a subsequent frame segment
`in the sub-sequence is inn-a coded so that the data which
`could not be accurately transmitted is no longer necessary.
`Dividing the moving image into sub-sequences reduces the
`required intra coded data from an entire frame to a frame
`segment. and therefore improves average compression e?i
`ciency.
`To reduce the amount of data aifected by a burst of
`channel errors. each digital code representing a frame seg
`ment in a sub-sequence is divided into data packets which
`have a length dynamically set according to an error rate on
`a transmission channel. Typically. the length is set so that the
`chance of transmitting the packet without error is sufficiently
`high. In addition to dynamically setting the packet length
`according to an error pattern on the channel. the frame rate
`and quantization steps size used for encoding the moving
`image can be dynamically adjusted to provide maximum
`frame rate and image quality for the effective capacity of the
`channel.
`To determine when a frame is ready for display. the
`receiver contains a status buffer which contains entries
`corresponding to the frame segments in several consecutive
`
`1. Field of the Invention
`This invention relates generally to coding. transmission.
`and display of video in telecommunication systems having
`bursty channel errors and in particular relates to mobile/
`wireless videophone systems.
`2. Description of Related Art
`Digital mobile/wireless telephones use mobile/wireless
`channels to transmit digital signals representing audio. Such
`signals are normally in the form of packets. More
`speci?cally. a sender transmits a signal representing packets
`of digital audio data where each packet represents 30 ms of
`audio; and a receiver decodes one packet every 30 ms to
`maintain continuous audio output. However. channel (or
`transmission) errors in the data packets can be as many as
`one bit in 103 to 102 which can interfere with the decoding
`process. Typically. channel errors for mobile/wireless tele
`phone channels tend to be bursty. that is the errors occur in
`bursts or groups that are clumped together. Such burst of
`errors may correspond to events such as an object becoming
`temporarily interposed between the sender and receiver. To
`correct for the channel errors. the packets contain error
`correction codes (ECCs) with which the receiver attempts to
`correct the errors.
`In some other types of data transmission systems. a
`receiver which detects errors in a data packet from a sender
`requests that the sender retransmit the data packet. A variety
`of retransmission strategies are available and include basic
`automatic repeat request (ARQ) and hybrid ARQ protocols.
`Examples of ARQ systems are described in “Error Control
`Coding: Fundamentals and Applications”. by Shu Lin and
`Daniel J. Costello. Jr.. copyright by Prentice-Hall. Inc.
`(1983) which is incorporated herein by reference in its
`entirety.
`Retransmission is typically not used for mobile/wireless
`telephones because retransmission introduces unacceptable
`delay jitter into the audio. For instance. a receiver must
`receive packets representing 30 ms of audio at a rate of one
`per 30 ms. Otherwise. skips and breaks appear in the audio.
`Buffering or temporarily storing data packets in the receiver
`allows some ?exibility in the timing of the data packets. but
`bu?ering delays generation of audio from the packet. If the
`delay is too large. it becomes noticeable to users and changes
`the pattern of telephone conversations. If the delay is small
`enough not to be noticed. there is insu?icient time to allow
`the receiver to request and receive a retransmitted data
`packet before the data is needed for audio generation.
`especially if a data packet must be retransmitted more than
`once before being received without errors.
`Accordingly. instead of retransmission. mobile/wireless
`telephones have used techniques such as algebraic error
`control coding for correction of channel errors and equal!
`unequal error protection coding to provide more error cor
`rection coding for the most critical data. With the error
`correction coding. retransmission is not required. and delay
`jitter caused by retransmission is avoided. Errors which
`cannot be corrected from the error correction codes cause
`static which is acceptable for most communications.
`Recently. systems have been proposed for digital mobile!
`wireless videophones wherein a sender transmits signals
`representing both audio and video. The systems have
`
`15
`
`20
`
`25
`
`35
`
`45
`
`50
`
`55
`
`65
`
`Ex. 1009 / Page 4 of 10
`
`

`

`5,768,533
`
`15
`
`25
`
`3
`?ames. Each entry indicates whether a digital code for a
`?ame segment has been received without errors and indi
`cates whether the ?ame segment is inter or intra coded. A
`?ame segment is considered displayable if the ?ame seg
`ment is intra coded and the code for the frame segment has
`been received without errors or if the frame segment is inter
`coded. the code for the ?ame segment has been received
`without errors. and the preceding ?ame segment in the same
`sub—sequence is displayable. Aframe is displayable if all the
`?ame segments in the ?ame are displayable. The receiver
`only displays the most recent displayable frame.
`Accordingly. some ?ames may be skipped which decreases
`the ?ame rate in the moving image. However. ?ame rate
`variation is less noticeable than the frame quality degrada
`tion common in other systems.
`In accordance with another aspect of the invention. the
`sender contains status counters which correspond to the
`sub-sequences. The status counters contain counts indicating
`the number of times that ?ame segments in the sub
`sequences have been inter coded. If any count exceeds a
`threshold. the next ?ame segment for the sub-sequence
`corresponding to the count is intra coded. This re?eshes the
`data in the receiver and removes any ?aws in the moving
`image caused by previous undetected channel errors.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 shows a communication system in accordance with
`an embodiment of the invention.
`FIG. 2 illustrates a moving image having an image area
`which is partitioned in accordance with an embodiment of
`the invention.
`FIG. 3 represents ?ame segments in ?ames of a moving
`image.
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`
`In accordance with an embodiment of the invention. a
`communications system includes a sender which transmits a
`series of video data packets to a receiver. The packets
`represent a sequence of ?ames which form a moving image.
`The receiver collects the packets ?om the sender and checks
`the packets for errors. When a packet is received without
`errors. the receiver sets an entry in a video status buffer to
`indicate that a packet for a particular portion of a frame is
`ready. When the receiver detects an error. the receiver
`requests that the sender retransmit the packet which con
`tained the error.
`The sender. in response to a retransmission request.
`immediately inserts the retransmitted video data packet into
`the series of packets transmitted to the receiver. Accordingly.
`the series of data packets may mix video data ?om different
`?ames. and the video status buffer in the receiver contains
`entries for several ?ames to track data packets for the
`di?erent ?ames. When entries in the video status buffer
`indicate all data needed for a ?ame has been received
`without errors. the ?ame is “displayable". i.e. ready to be
`decoded and/or displayed The receiver periodically checks
`the video status buffer to determine if any ?ames are
`displayable. If one or more is displayable. the receiver
`decodes and displays the newest of the displayable ?ames.
`Generally. ?ames are displayed without errors because
`each data packet required for each ?ame displayed is
`without detectable error. Accordingly. ?awed areas in the
`displayed moving image are avoided. Further. inter coding
`can be used without ?aws accumulating in a displayed
`
`30
`
`35
`
`50
`
`55
`
`65
`
`4
`image. The video data packets are relatively small when
`compared to the data required to represent an entire ?ame.
`and usually a retransmitted packet is received in time to
`display a ?ame without a delay or a change in the ?ame rate.
`Occasionally. display of a ?ame may be skipped or delayed
`which reduces or causes jitter in the ?ame rate of the
`displayed moving image. However. the change in the ?ame
`rate still provides an acceptable moving image for most
`videophone applications where fast motion and a high ?ame
`rate are not required. Additionally. the use of inter coding
`can improve video compression e?iciency and allow a
`higher maximum ?ame rate than possible systems using less
`e?icient video compression. The higher maximum ?ame
`rate at least partially compensates for loss of ?ames.
`FIG. 1 shows a block diagram of a sender 150 and a
`receiver 100 which communicate via a channel 145. In one
`embodiment of the invention. one of sender 150 and receiver
`100 is in a mobile/wireless videophone. and the other of
`receiver 100 and sender 150 is in a public switched tele
`phone network (PSTN) videophone. In other embodiments
`of the invention. sender 150 and receiver 100 are both in
`mobile/wireless videophones or both in PS'I'N videophones.
`FIG. 1 shows the portions of two videophones that are
`required for one-way video transmission. To allow two-way
`video transmission over channel 145. each videophone
`would contain a transmitting portion similar or identical to
`sender 150 and a receiving portion similar or identical to
`receiver 100.
`Sendu 150 receives an input video signal from a video
`source 155. The input video signal represents a sequence of
`?ames where each ?ame is a still image. A time index orders
`the ?ames. and when displayed in sequence. the ?ames
`provide the illusion of an image containing moving objects.
`Thus. the sequence of ?ames are referred to herein as a
`moving image. Sender 150 encodes the moving image and
`transmits via channel 145 a signal representing the moving
`image.
`In a mobile/wireless or PS'I'N videophone. video source
`155 contains a video camera and an analog-to-digital con
`verter capable of providing a digital signal representing a
`moving image. An input bu?er 160 stores data representing
`the digital signal ?om video source 155. Data representing
`video can have a variety of formats. In one embodiment of
`the invention. each ?ame in the moving image is represented
`by one or more two-dimensional arrays of pixel values
`which are stored in input buffer 160. Each pixel value in a
`two-dimensional array represents an intensity. color. or color
`component for a small area or picture element having a
`position in a ?ame corresponding to the position of the pixel
`value in the two-dimensional array. For example. a ?ame
`can be represented by a single two-dimensional array of
`pixel values wherein each pixel value represents a set of
`three RGB or YUV color components which identify a color
`for a corresponding picture element. Alternatively. a ?ame
`can be represented by three arrays. one corresponding to
`each of three color components RGB or YUV.
`FIG. 2 represents an image area 2200 for a moving image.
`Image area 200 contains a two-dimensional array of picture
`elements (or pixels) which are represented by a two
`dirnensional array of corresponding pixel values. For
`example. in a format referred to in the art as QCIF. image
`area 200 is divided into 176x 144 pixels which correspond to
`x co-ordinates ranging ?om 0 to 175 and y co-ordinates
`ranging ?om 0 to 143.
`A time index t orders the ?ames of a moving image into
`a sequence as shown in FIG. 3. For a conventional video
`
`Ex. 1009 / Page 5 of 10
`
`

`

`5
`camera. the frame rate of a moving image is 30 frames per
`second. However. for videophones where the available
`bandwidth for transmission is relatively small. a lower frame
`rate of about 7 frames per second is typically used. Since
`display of fast motion is usually not required for
`videophones. 7 frames/sec provides a moving image with
`reasonably smooth motion. Sender 150 selects from the
`input video signals (or from input buffer 160) enough frames
`to provide a moving image having a desired frame rate. For
`example. if video source 155 provides 30 frames per second.
`a video encoder 170 encodes every fourth frame to provide
`a frame rate of 7.5 frames per second.
`In accordance with an embodiment of the invention. a
`moving image is partitioned into sub-sequences by parti
`tioning the image area of the moving image into regions.
`FIG. 2 shows an exemplary embodiment where image area
`200 is partitioned into nine regions 210 to 218. and the
`portions of the moving image which correspond to regions
`210 to 218 are the sub-sequences of the moving image. In
`the exemplary embodiment. each region 210 to 218 is a strip
`as wide (along an x direction) as image area 200 and one
`ninth the height (along a y direction) of area 200. so that for
`the QCIF format. each region is 176x16 pixels.
`Alternatively. any number or shape may be used for the
`regions which divide a moving image into sub-sequences.
`FIG. 3 shows frames 300 to 304 which contain frame
`segments 310 to 314 respectively that are part of a sub
`sequence.
`Video encoder 170 generates separate digital codes for
`each frame segment. The coding process encodes the frame
`segments separately from each other to allow decoding of
`each sub-sequence without using information from other
`sub-sequences. In effect. each sub-sequence is an separate
`moving image for which any video compression process
`desired may be employed. In one embodiment. video
`encoder 170 uses a standard video encoding protocol
`referred to as H.263 which is described in Draft lTU-T
`Recommendation H.263. entitled “Video Coding For Low
`Bitrate Communication.” Jul. 5. 1995. which is incorporated
`by reference herein in its entirety.
`When encoding a frame segment. video encoder 170
`checks status counters 165 to determine if the frame segment
`should be “intra” coded. Counters 165 are in one-to-one
`correspondences with the regions that de?ne the sub
`sequences and the frame segments. A count in a counter
`being high indicates a corresponding frame segment should
`be intra coded to ensure that receiver 100 is not building on
`data containing errors. Also associated with each counter in
`counters 165 is a set of status ?elds which indicates the type
`of coding used for recently encoded frame segments.
`To intra code a frame segment. video encoder 170 uses a
`still image encoding process to generate a digital code
`representing the frame segment. In the exemplary
`embodiment. video encoder 170 partitions the frame seg
`ment into macroblocks. where each macroblock has the
`same size such as 8X8 or 16x 16 pixels. and then compresses
`the macroblock. For example. a discrete cosine transform
`(DCI') of the pixel values for a macroblock followed by
`quantization and run length coding typically provides a bit
`stream which requires less bandwidth to transmit than would
`all of the pixel values in the macroblock. Compressed data
`from the macroblocks are combined according to an encod
`ing syntax to form a digital code for the frame segment. The
`digital code for an intra coded frame segment represents all
`of the information required for decoding that frame segment.
`Accordingly. the digital code for an intra coded frame
`segment refreshes the data used by receiver 100 for a
`
`45
`
`50
`
`55
`
`65
`
`5,768,533
`
`10
`
`20
`
`25
`
`30
`
`35
`
`6
`sub-sequence. and any channel errors in previous frames do
`not a?‘ect subsequent decoding.
`Inter coding typically provides better compression than
`does intra coding. To inter code a frame segment. video
`encoder 170 divides the frame segment into macroblocks.
`and then performs motion estimation on each macroblock.
`Motion estimation for a macroblock ?nds a motion vector
`which points from the location of the macroblock to the
`location of a best fit block which is within the corresponding
`frame segment of the preceding frame. To allow motion
`vectors and best fit blocks which extend outside the bound
`aries of a sub-sequence. pixel values for pixels at the edge
`of the preceding frame segment are repeated to ?ll in an area
`of a best ?t block which is outside a frame or in another
`sub-sequence. Accordingly. the best ?t block contains only
`data from a single sub-sequence. and data from other sub
`sequences is not used in the motion estimation process.
`If a good best ?t block is found. pixel values in the best
`fit block are subtracted from corresponding pixel values in
`the macroblock to generate a difference block. The dilfer
`ence block is then compressed. for example. by a DCT
`followed by quantization and run length coding. A resulting
`digital code for the frame segment indicates the motion
`vector for the macroblock and the information from the
`difference block. If a good best ?t is not found for a
`macroblock. that macroblock is intra coded in the same
`manner as the macroblocks in an intra coded frame segment.
`Thus. inter coded frame segments can contain inter coded
`macroblocks and intra coded macroblocks. If all of the
`macroblocks in a frame segment are intra coded. the frame
`segment is intra coded.
`Each time a frame segment is inter coded. video encoder
`170 increments the one of counters 165 which corresponds
`to the frame segment. by an amount equal to the di?erence
`in time indices of successive encoded frames. For example.
`if every fourth frame from video source 155 is encoded. one
`of counters 165 is incremented by four each time a frame
`segment is inter coded. Video encoder 170 resets the corre
`sponding counter each time a frame segment is intra coded.
`If a count corresponding to a sub-sequence exceeds a
`threshold Tum“. the next frame segment for the sub
`sequence should be intra coded to refresh the data used by
`receiver 100. Incrementing by an amount proportional to the
`difference in time indices of encoded frames ensures that the
`refresh occurs at regular intervals even if sender 150 varies
`the frame rate.
`Typically. intra coding reduces video compression
`efficiency. and if several frame segments in a frame are intra
`coded. display of the frame can be delayed because trans
`mission of a bit stream representing the frame takes longer
`than allowed. Accordingly. if several frame segments of a
`frame should be intra coded. video encoder 170 can select
`one or a few of the frame segments for intra coding. Other
`frame segments can be intra coded in the next frame.
`The digital code representing a frame segment is part of
`the bit stream which is transmitted to receiver 100. Video
`encoder 170 counts bits generated during encoding and
`breaks the bit stream for a frame segment into data packets
`which are shorter than a threshold length THC-Km. The
`packet length affects the chance that a channel error will
`occur during a transmission. and in one embodiment of the
`invention. threshold packet length TPACKET is dynamically
`selected according to an error rate on channel 145. When the
`error rate is high. threshold length Tmcm is decreased so
`that the chance of a packet being transmitted without errors
`remains high. and the output video frame rate at receiver 100
`
`Ex. 1009 / Page 6 of 10
`
`

`

`10
`
`15
`
`25
`
`35
`
`45
`
`7
`remains above a minimum level (about 3 frames/second)
`with a frame delay of less than a few hundred milliseconds.
`When the error rate is low. threshold length TPACKET is
`increased up to a limit where there is one video data packet
`per frame segment.
`The portion of a frame segment represented by a single
`data packet is referred to herein as a sub-segment. ‘Typically.
`each sub-segment contains an integral number of macrob
`locks. Using an integral number of macroblocks per data
`packet relates the data packets to de?nite image areas and
`allows receiver 100 to track data packets which have been
`correctly received. The number of macroblocks varies from
`sub-segment to sub-segment. and the areas of a moving
`image represented by the sub-segments vary from frame to
`frame.
`Video encoder 170 adds a video header and a cyclic
`redundancy code (CRC) to each data packet. The header
`identi?es the frame. sub-sequence. and sub-segment
`described by the packet. In the exemplary embodiment. the
`video header contains: a start ?eld which contains a unique
`pattern marking the start of a data packet; a time index ?eld
`(4 bits) identifying a frame; a sequence number ?eld (4 bits)
`identifying a sub-sequence so that the combination of the
`time index and sequence number ?elds identify a frame
`segment; a sub-segment start and end ?elds (8 bits) identi
`fying a sub-segment by numbers of the ?rst and last mac
`roblocks described by the data packet; and a coding process
`held (1 bit) indicating how the frame segment was encoded
`(intra or inter coded). In addition to the video header. a Tx
`header may be added for transmission on channel 145. and
`information which is in both the video header and the Tx
`header can be deleted from the video header. Following the
`video header is the digital code which video encoder 170
`generates to describe the sub-segment identi?ed by the video
`header. The CRC. which receiver 100 uses to detect channel
`errors in the video data packets. is generated from the digital
`code. In addition to the CRC. an error correction code can
`be added to each data packet to provide receiver 100 with
`error detection and error correction capabilities.
`Data packets from video encoder 170 are written to a
`transmitting buffer 180 and to a ?rst-in-?rst-out (FIFO)
`buffer 190. When FIFO bu?'er 190 over?ows. the oldest data
`packets in FIFO buffer 190 are pushed out to make room for
`newly encoded data packets. As described below. a retrans
`mission controller 185 determines whether transmission
`buffer 180 or FIFO buffer 190 provides data for the bit
`stream which is transmitted to receiver 100 via channel 145.
`Channel 145 is a two-way channel including a sub-channel
`145B for data ?ow from sender 150 to receiver 100 and a
`sub-channel 145A for data ?ow from receiver 100 to sender
`150. In the exemplary embodiment. channel 145 is a mobile!
`wireless channel. and sub-channels 145A and 14513 are time
`multiplexed for video and audio data. Many systems are
`commercially available which can create wireless/mobile
`channels such as DECI‘. GSM. TE'I'RA. and PDC which are
`suitable for digital video transmission. However. embodi
`ments of the invention can use any type of communication
`channel and are not limited to mobile/wireless channels.
`Receiver 106 contains a receiving bu?‘er 130 which holds
`data packets from sender 150 and checks the CRC of the
`data packets to detect errors. The results of the CRC
`checking is sent to a request controller 125 and to a status
`buffer 115. Error can also be detected in the data packets
`when a video decoder 120 parses or decodes all or part of the
`data packet to identify syntax errors. When a syntax error
`occurs. video decoder 120 sets an entry in status buffer 115
`which is then passed to request controller 125. In the
`
`50
`
`SS
`
`65
`
`5,768,533
`
`8
`exemplary embodiment. request controller 125 sends a
`retransmission request to sender 150 only if a data packet
`contains an error and does not send any message or acknowl
`edgement to sender 150 when a data packet is received
`without errors. This retransmission strategy is commonly
`referred to as negative acknowledgments (NAK). In other
`embodiments of the invention. more complex retransmission
`strategies such as hybrid automatic repeat requests can be
`employed.
`Before sending a retransmission request. request control
`ler 125 checks status bulTer 115 to determine whether the
`data packet which contained the error is needed. A data
`packet which has a time index prior to the time index of a
`displayable frame corresponds to a frame that has been
`skipped and is therefore not need. A data packet which has
`a time index prior to the time index of an intra coded frame
`segment. whether received correctly or not. is not needed
`because when the intra coded frame segment is correctly
`received. the sub-sequence is refreshed and the previous data
`packets are not needed. Request controller 125 does nothing
`if the data packet is not needed. Otherwise. request control
`ler 125 transmits to sender 150 a request for retransmission
`of the data packet.
`The retransmission request identi?es the frame. sub
`sequence. and sub-segment described by the data packet
`containing the error and can. for example. take the same
`form as the video header for the data packet containing the
`error. As indicated above. typically sub-channel 145A is
`time multiplexed for video and audio data. and request
`controller 125 must compete with an audio system (not
`shown) and a video transmitter (not shown) for access to
`channel 145A. Retransmission requests take priority over
`video data packets which are awaiting transmission.
`When sender 150 receives a retransmission request.
`retransmission controller 185 searches FIFO buffer 190 for
`the data packet requested. If the requested data packet is
`found. retransmission controller 185 then checks the status
`?elds for the sub-sequence described by the data packet to
`determine whether a frame segment in the sub-sequence was
`intra coded after transmission of the data packet containing
`the error. If so. retransmission controller 185 ignores the
`request. Otherwise. the requested data packet is retransmit
`ted from FIFO buffer 190 to receiver 100. The retransmitted
`data packet has priority over freshly encoded data packets
`from transmission buffer 180 so that transmission begins
`immediately following the end of a currently transmitted
`data packet. The retransmission controller 185 also sets a
`status ?ag in status counters 165 to indicate the requested
`data packet has been retransmitted. If retransmission con
`troller 185 ?nds that the retransmission is not the ?rst for the
`requested data packet. retransmission controller 185
`requests that video encoder 170 intra code the next frame
`segment of the sub-sequence represented by the requested
`data packet. If the requested data packet is not available in
`F